有好多题之前写过所以有记录没有写帖子记录但写在笔记本上的。贪心算法的核心思想是在每一步选择中都采取当前状态下最优的选择从而希望导致全局最优解。以下均为自己AC的代码。P2240 【深基12.例1】部分背包问题算法思路这是一个典型的贪心算法问题。物品可以分割所以优先选择单位价值最高的物品装入背包直到背包装满为止。#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n,t; cinnt; vectorpairint,doublev(n); for(int i0;in;i) { int vul; cinv[i].firstvul; v[i].second1.0*vul/v[i].first; } sort(v.begin(),v.end(),[](const pairint,doublea,const pairint,doubleb){ return a.secondb.second; }); int sum0; double re0; for(int i0;in;i) { sumv[i].first; if(sumt) { rev[i].first*v[i].second; } else { re(v[i].first-sumt)*v[i].second; break; } } coutfixedsetprecision(2)re; return 0; }P1208 [USACO1.3] 混合牛奶 Mixing Milk算法思路按照牛奶单价从小到大排序优先购买单价便宜的牛奶直到满足需求量。#includebits/stdc.h using namespace std; typedef long long ll; int main() { ll n,m; vectorpairint,llv; cinnm; for(int i0;im;i) { int p; ll a; cinpa; v.push_back({p,a}); } sort(v.begin(),v.end()); ll need n; ll cost 0; for(auto t : v) { if(need 0) break; int price t.first; ll amount t.second; if(amount need) { cost 1LL * price * amount; need - amount; } else { cost 1LL * price * need; need 0; } } cout cost endl; return 0; }P1223 排队接水算法思路让接水时间短的人先接水这样可以减少后面人的等待时间从而最小化平均等待时间。#includebits/stdc.h using namespace std; typedef long long ll; int main() { int n; cin n; vectorpairint, int v; for(int i 1; i n; i) { int t; cin t; v.push_back({t, i}); } sort(v.begin(), v.end()); for(int i 0; i n; i) { if(i 0) cout ; cout v[i].second; } cout endl; ll sum_wait 0; ll pre_time 0; for(int i 0; i n; i) { sum_wait pre_time; pre_time v[i].first; } double avg 1.0 * sum_wait / n; printf(%.2f\n, avg); return 0; }P1803 凌乱的yyy / 线段覆盖算法思路按照活动结束时间从小到大排序选择结束时间最早且不与已选活动冲突的活动这样可以安排尽可能多的活动。#includebits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); long long n; cinn; vectorpairint,intv(n); for(int i0;in;i) { cinv[i].firstv[i].second; } sort(v.begin(),v.end(),[](const pairint,inta,const pairint,intb){ return a.secondb.second; }); int coverv[0].second; int step0; int num0; for(int i1;in;i) { stepv[i].first; if(stepcover) { num; coverv[i].second; } } coutnum1endl; return 0; }P3817 小 A 的糖果算法思路从左到右遍历糖果数组如果相邻两堆糖果之和超过限制优先从右边一堆中减少糖果如果不够再从左边一堆中减少。未完全AC版本#includebits/stdc.h using namespace std; typedef long long ll; int main() { int n, x; cin n x; vectorll a(n); for(int i 0; i n; i) { cin a[i]; } ll ans 0; for(int i 1; i n; i) { if(a[i-1] a[i] x) { ll delta a[i-1] a[i] - x; ans delta; a[i] - delta; } } cout ans endl; return 0; }完全AC版本#includebits/stdc.h using namespace std; typedef long long ll; int main() { int n, x; cin n x; vectorll a(n); for(int i 0; i n; i) { cin a[i]; } ll ans 0; for(int i 1; i n; i) { ll sum a[i-1] a[i]; if(sum x) continue; ll need_cut sum - x; ll max_right a[i]; if(need_cut max_right) { a[i] - need_cut; ans need_cut; } else { ans max_right; ll left_cut need_cut - max_right; a[i-1] - left_cut; ans left_cut; a[i] 0; } } cout ans endl; return 0; }P1090 [NOIP 2004 提高组] 合并果子算法思路使用小根堆优先队列每次取出最小的两个数合并将合并后的结果放回堆中重复直到只剩一堆累计每次合并的代价。小根堆栈与队列中有记录#includebits/stdc.h using namespace std; int main() { int n; cin n; priority_queueint, vectorint, greaterint q; for(int i 0; i n; i) { int x; cin x; q.push(x); } long long ans 0; while(q.size() 1) { int a q.top(); q.pop(); int b q.top(); q.pop(); int sum a b; ans ans sum; q.push(sum); } cout ans endl; return 0; }以后看到有很多堆 / 文件 / 木板 / 节点每次合并两个合并代价等于两者之和合并后的新对象还会继续参与合并要求所有合并总代价最小应该立刻想到每次取当前最小的两个 ↓ 合并 ↓ 重新放回对应数据结构小根堆核心触发信号反复合并 代价为两者之和 求总代价最小 Huffman 贪心。其实感觉没什么写的都记在笔记本上了就不补充了