洛谷 B4051：[GESP202409 五级] 小杨的武器 ← 贪心算法

【题目来源】https://www.luogu.com.cn/problem/B4051【题目描述】小杨有 n 种不同的武器他对第 i 种武器的初始熟练度为 ci。小杨会依次参加 m 场战斗每场战斗小杨只能且必须选择一种武器使用假设小杨使用了第 i 种武器参加了第 j 场战斗战斗前该武器的熟练度为 ci′则战斗后小杨对该武器的熟练度会变为 ci′aj。需要注意的是aj 可能是正数0 或负数这意味着小杨参加战斗后对武器的熟练度可能会提高也可能会不变还有可能降低。小杨想请你编写程序帮他计算出如何选择武器才能使得 m 场战斗后自己对 n 种武器的熟练度的最大值尽可能大。【输入格式】第一行包含两个正整数 n,m含义如题面所示。第二行包含 n 个正整数 c1,c2,…cn代表小杨对武器的初始熟练度。第三行包含 m 个正整数 a1,a2,…am代表每场战斗后武器熟练度的变化值。【输出格式】输出一个整数代表 m 场战斗后小杨对 n 种武器的熟练度的最大值最大是多少。【输入样例】2 29 91 -1​​​​​​​【输出样例】10​​​​​​​【数据范围】对全部的测试数据保证 1≤n,m≤10^5−10^4≤ci,ai≤10^4。【算法分析】● 通过‌局部最优选择‌正收益加给最大负收益加给最小保证了最终最大值的全局最优性是解决此问题的标准方法。● 题目‌没有限制每种武器只能使用一次‌武器可以在不同战斗中被重复选择。样例解释的方案只是展示了其中一种最优分配方式并不隐含“每种武器只能用一次”的限制。​​​​​​​【算法代码】#include bits/stdc.h using namespace std; int mxINT_MIN; int n,m,x; int main() { cinnm; for(int i1; in; i) { cinx; mxmax(mx,x); } for(int i1; im; i) { cinx; if(n1) mxx; else if(x0) mxx; } coutmxendl; return 0; } /* in: 2 2 9 9 1 -1 out: 10 */【参考文献】https://gesp.ccf.org.cn/101/attach/1633836261703712.pdfhttps://www.luogu.com.cn/problem/solution/B4051