普通贪心:
改题步骤:
1.输入解析:
* 读 n(需求数量)、m(农户数);
* 读 m 行,每行 p a(单价、可售量)。
2.贪心策略:
* 将农户按 单价 pip^{i}pi 升序排序(单价低者优先);
* 依次购买:每次取 min(剩余需求, 当前农户可售量) 单位,累加花费;
* 若某次购买后需求降为 0,则终止。
3.数据结构选择:
* 使用 vector<pair<int, int>> farmers,存 (price, amount);
* sort(farmers.begin(), farmers.end()) —— pair 默认按 first(price)升序排 ✅
4.时间复杂度:
* 排序:O(mlogm),m≤5000 → 极快;
* 贪心扫描:O(m);
* 总复杂度:O(mlogm),最优。
改过的进阶贪心: