问题:

${假设你选n件物品,选这个物品的价值是a_i,不选这个物品你将失}$
${去b_i,问你选m件物品得到的价值最大是多少?}$

解决方案:

${按a_i+b_i排序,选m个最大的就好.}$

证明:

${假设你当前值为0,得到一个值你将+a_i,失去一个值你}$
${将(-b_i),那么这件物品对于你答案的影响就是a_i+b_i的.}$

${用交换的方法更好理解,假如我选现在有n件物品,物}$
${品i:a_{i},b_{i}.物品i+1:a_{i+1},b_{i+1}.假如我现在只}$
${能在这两件物品中选一件,选i而不选i+1,那么我得到}$
${的价值就是(a_i-b_{i+1}),同理另外一种选i+1而不选i}$
${得到的答案吧是(a_{i+1}-b_{i}),假设我选第一个}$
${的优先级要大于第二个的话,且当(a_i-b_{i+1})>(a_{i+1}-b_{i})时}$
${成立,移项就是(a_i+b_{i})>(a_{i+1}+b_{i+1})成立.}$

后记:

${遇到很多次了,希望都能秒了这种贪心.}$

一个简单的贪心问题

问题:

解决方案:

证明:

后记: