菜题。最简单的排序＋贪婪就可以过。但是有一些陷阱。

是贡献了三次wa。我居然把忘了把调试部分注释掉—_—

#include <cstdio>

int n, m, a[1000], b[1000];
double r[1000];

void pt()
{
 for(int i = 0; i < m; i ++)
 {
  printf("%d %d %0.3f\n", a[i], b[i], r[i]);
 }
}

int main()
{
 //freopen("in.txt", "r", stdin);
 while(scanf("%d %d", &n, &m) && n != -1)
 {
  int i, k, j;
  for(i = 0; i < m; i ++)
  {
   scanf("%d %d", &a[i], &b[i]);
   if(b[i] == 0) r[i] = 99999999;
   else
    r[i] = double(a[i]) / double(b[i]);
  }
  //select sort
  for(i = 0; i < m - 1; i ++)
  {
   double mx = r[i]; j = i;
   for(k = i + 1; k < m; k ++)
   {
    if(r[k] > mx)
    {
     j = k;
     mx = r[k];
    }
   }
   int ai = a[i], bi = b[i]; double rd = r[i];
   a[i] = a[j], b[i] = b[j]; r[i] = r[j];
   a[j] = ai, b[j] = bi; r[j] = rd;
  }
  //pt();
  double sum = 0; int si = n;
  for(i = 0; i < m; i ++)
  {
   if(si >= b[i])
   {
    si -= b[i];
    sum += double(a[i]);
   }
   else
   {    
    sum += r[i] * double(si);
    si = 0;
   }
   if(si == 0)
    break;
  }
  printf("%0.3f\n", sum);
 }
 return 0;
}

评论