本题基本上就是背包问题的变化，背包求最大价值，此题求最小花费，没差别，贪心！
快排我想自己写，结果用了very long long time~~囧！结果第一次提交超时，调试发现快排还是错了，有死循环，杯了个具，基础太不扎实！
/* ID: LANG: C TASK: milk */ #include <stdio.h> #include <stdlib.h> #include <string.h> #define SZ 5000 typedef struct { int price; int amount; }farmer; void quicksort(farmer *p, int low, int high) { if(low >= high) return; farmer tmp = p[low]; int i = low; int j = high; while(i < j) { while(i < j && tmp.price < p[j].price) j--; //if(tmp.price > p[j].price) { //dead loop if equal cause i & j didn't change if(i < j) { p[i] = p[j]; //p[j] = tmp; i++; } while(i < j && tmp.price > p[i].price) i++; //if(tmp.price < p[i].price) { if(i < j) { p[j] = p[i]; //p[i] = tmp; j--; } } p[i] = tmp; quicksort(p, low, i - 1); quicksort(p, i + 1, high); } int main() { FILE *fin = fopen("milk.in", "r"); FILE *fout = fopen("milk.out", "w"); int N, M; int i, opt; farmer frm[SZ]; fscanf(fin, "%d %d", &N, &M); for(i = 0; i < M; i++) fscanf(fin, "%d %d", &frm[i].price, &frm[i].amount); quicksort(frm, 0, M - 1); i = opt = 0; while(N > 0) { if(N >= frm[i].amount) { opt += frm[i].price * frm[i].amount; N -= frm[i].amount; i++; } else { opt += frm[i].price * N; N = 0; } } fprintf(fout, "%d/n", opt); exit(0); }
分析的解法一跟我的想法一样，不说了。。。
分析的解法二比较巧妙，因为价格最大也就1000，所以把所有farmers的供给量按照价格累加在一起，然后遍历价格数组即可，这样时间复杂度可以达到O(n)，因为我的方法用了快排，所以最好情况是O(nlogn)。
分析的解法三也是O(n)的解法，使用了计数排序(完全忘了！)，代码不知道用什么语言写的，看不懂。。。
分析的解法四，五跟解法二思路是一样的，只不过写的更简洁一点，复杂度为O(1000, M)
