2012463 2006-08-10 00:50:36 Accepted 2109 C++ 00:00.17 408K St.Crux 菜题。最简单的排序＋贪婪就可以过。但是有一些陷阱。 是贡献了三次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;}    

评论