学步园

本题基本上就是背包问题的变化，背包求最大价值，此题求最小花费，没差别，贪心！

快排我想自己写，结果用了very long long time~~囧！结果第一次提交超时，调试发现快排还是错了，有死循环，杯了个具，基础太不扎实！

/*<br /> ID:<br /> LANG: C<br /> TASK: milk<br /> */<br /> #include <stdio.h><br /> #include <stdlib.h><br /> #include <string.h><br /> #define SZ 5000<br /> typedef struct {<br /> int price;<br /> int amount;<br /> }farmer;<br /> void quicksort(farmer *p, int low, int high) {<br /> if(low >= high)<br /> return;<br /> farmer tmp = p[low];<br /> int i = low;<br /> int j = high;<br /> while(i < j) {<br /> while(i < j && tmp.price < p[j].price) j--;<br /> //if(tmp.price > p[j].price) { //dead loop if equal cause i & j didn't change<br /> if(i < j) {<br /> p[i] = p[j];<br /> //p[j] = tmp;<br /> i++;<br /> }<br /> while(i < j && tmp.price > p[i].price) i++;<br /> //if(tmp.price < p[i].price) {<br /> if(i < j) {<br /> p[j] = p[i];<br /> //p[i] = tmp;<br /> j--;<br /> }<br /> }<br /> p[i] = tmp;<br /> quicksort(p, low, i - 1);<br /> quicksort(p, i + 1, high);<br /> }<br /> int main() {<br /> FILE *fin = fopen("milk.in", "r");<br /> FILE *fout = fopen("milk.out", "w");<br /> int N, M;<br /> int i, opt;<br /> farmer frm[SZ];<br /> fscanf(fin, "%d %d", &N, &M);<br /> for(i = 0; i < M; i++)<br /> fscanf(fin, "%d %d", &frm[i].price, &frm[i].amount);<br /> quicksort(frm, 0, M - 1);<br /> i = opt = 0;<br /> while(N > 0) {<br /> if(N >= frm[i].amount) {<br /> opt += frm[i].price * frm[i].amount;<br /> N -= frm[i].amount;<br /> i++;<br /> }<br /> else {<br /> opt += frm[i].price * N;<br /> N = 0;<br /> }<br /> }<br /> fprintf(fout, "%d/n", opt);<br /> exit(0);<br /> }<br />  

分析的解法一跟我的想法一样，不说了。。。

分析的解法二比较巧妙，因为价格最大也就1000，所以把所有farmers的供给量按照价格累加在一起，然后遍历价格数组即可，这样时间复杂度可以达到O(n)，因为我的方法用了快排，所以最好情况是O(nlogn)。

分析的解法三也是O(n)的解法，使用了计数排序(完全忘了！)，代码不知道用什么语言写的，看不懂。。。

分析的解法四，五跟解法二思路是一样的，只不过写的更简洁一点，复杂度为O(1000, M)