XMU1316.卡车装货 垃圾水题 给我的反思
1316.卡车装货Time Limit: 1000 MS Memory Limit: 65536 K
Total Submissions: 516 (104 users) Accepted: 117 (93 users)
[ My Solution] Description

有一辆最大载重M公斤的卡车和N种货物，已知第i种货物有wi公斤,其总价值为vi元。每种货物都可以取任意数量装入卡车。试确定装货方案，使得装入卡车的所有物品总价值最大。

Input

第一行是两个整数M，N(0<M,N<100000)。接下来的N行，每一行有两个整数wi，vi(0<wi<=100,0<vi<=100)，分别代表第i种货物的总重量和总价值。

Output

输出卡车能装入货物的最大价值，保留6位小数。

Sample Input

10 3

10 10

5 6

20 50

Sample Output

25.000000

猛的一看还以为是背包 就使劲的用背包 搞 但是没有搞出25是怎么得到的

其实这不是个背包问题 而是贪心 就是因为不仔细看题 以及没有分析样例造成的做了很多无用功

最重要的是没有测试样例 就直接写程序

以前也经常犯这样的错误 等把程序写好了 忽然发现样例不对 然后发现 原来看错题了

这下就辛苦努力数十年 一朝回到解放前

多多做这么多无用功 还不如认真读题

分析样例

教训：以后每做一个题 都要搞清楚样例是如何得到的之后才能拍代码

#include<stdio.h>#include<string.h>#include<stdlib.h>struct haha{double cost;double val;double cmp;}a[1000000+100];int bag[100000];int cp(const void *a,const void *b){return (*(struct haha*)b).cmp>(*(struct haha*)a).cmp?1:-1;}int main(){    int m,i;double ans,n;while(scanf("%lf %d",&n,&m)!=EOF){ans=0;          for(i=0;i<m;i++)  {  scanf("%lf %lf",&a[i].cost,&a[i].val);  a[i].cmp=a[i].val/a[i].cost;  }  qsort(a,m,sizeof(a[0]),cp);  for(i=0;i<m;i++)  {  if(n<=0) break;  if(a[i].cost<=n)  {  ans+=a[i].val;n=n-a[i].cost;  }  else  {                   ans+=a[i].cmp*n;n=0;  }  }  printf("%lf\n",ans);}return 0;}