http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1109
按收益排序 贪心选择 收益最大的 交易 不够的话 按比例交易
用c语言 写了一次 hdu 上 WA zoj 超时
c++ STL 今天刚看 很好用
#include <iostream> #include <fstream> #include <vector> #include <algorithm> using namespace std; struct Mouse { double j,f; double shouyi; }; bool comp(const Mouse &d1,const Mouse &d2){ if(d1.shouyi != d2.shouyi) return d2.shouyi < d1.shouyi; return d2.f > d1.f; } int main(){ ifstream cin("2109.txt"); vector<Mouse> v; Mouse mouse; int m,n,i; cout.precision(3); //三位小数 double sum; while(cin >> m >> n){ if(m == -1 && n == -1) break; v.clear(); sum = 0.0; for(i = 0; i < n; ++i){ cin >> mouse.j >> mouse.f; mouse.shouyi = mouse.j / mouse.f; v.push_back(mouse); } sort(v.begin(),v.end(),comp); for(i = 0; i < v.size(); i++){ if(m >= v[i].f){ sum += v[i].j; m -= (int)v[i].f; } else { sum += m * v[i].shouyi; break; } } cout << fixed << sum << endl; } system("PAUSE"); return 0; }
