1118 AlvinZH's Fight with DDLs II
思路
中等题，贪心。
理解题意，每次攻击中，可以使某个敌人生命值-1，自己生命值减去∑存活敌人总攻击力。
贪心思想，血量少攻击高的要先消灭，所以以A/L作为参数排序，即将所有的敌人根据A/L从大到小排序。
遍历一次，对于排序好的敌人，HP减去（总攻击*该敌人血量），总攻击减去该敌人攻击。代码如下：
HP -= (sumA * H[i].L);
sumA -= H[i].A;
if(HP <= 0) break;
分析
贪心证明：对于已经排好序的序列，HP总消耗为 \(\sum_{i = 1}^{n}\sum_{j = i}^{n}\left ( H[i].L*H[j].A \right )\) 。
如果我们交换其中相邻两个的位置，位置设为x,y，HP消耗与原来相比，有影响的也只有i=x和i=y两项，原来是 \(H[x].L*\sum_{j=x}^{n}H[j].A + H[y].L*\sum_{j=y}^{n}H[j].A\) ，而现在变成了\(H[y].L*\sum_{j=x}^{n}H[j].A + H[x].L*\left ( H[x].A+\sum_{j=y+1}^{n}H[j].A \right )\) ，其他未变，后者减去前者，得到\(H[y].L*H[x].A-H[x].L*H[y].A\) ，依照排序来看，有 \(\frac{H[x].A}{H[x].L} \geq \frac{H[y].A}{H[y].L}\) ，所以后者减去前者的值是大于等于0的。
由此可以证明：如果相邻两个交换，会导致HP总消耗增加。任何的一个攻击敌人次序，都可以在已排好序的次序上通过多次上述交换（相邻，且索引值小的后移）得到，由此可以判断所有的攻击次序HP消耗值都大于等于原排序攻击次列。
贪心得证，至于如何多次交换，可参考冒泡排序过程。
时间复杂度：O(nlgn)。
空间复杂度：O(n)。
参考代码
/*
Author: 朱辉(35)
Result: AC Submission_id: 514527
Created at: Mon Dec 25 2017 03:09:00 GMT+0800 (CST)
Problem: 1118 Time: 4 Memory: 2840
*/
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
struct Hero {
int A, L;
bool operator < (const Hero h) const {
return 1.0 * A/L > 1.0 * h.A/h.L;
}
};
int n, HP;
Hero H[1005];
int main()
{
while(~scanf("%d %d", &n, &HP))
{
int sumA = 0;//总攻击力
for (int i = 0; i < n; ++i) {
scanf("%d %d", &H[i].A, &H[i].L);
sumA += H[i].A;
}
sort(H, H+n);
for (int i = 0; i < n; ++i) {
HP -= (sumA * H[i].L);
sumA -= H[i].A;
if(HP <= 0) break;
}
if(HP > 0) printf("YES\n");
else printf("NO\n");
}
}