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");

    }

}

巴特西

2016级算法期末上机-F.中等·AlvinZH's Fight with DDLs II

1118 AlvinZH's Fight with DDLs II

思路

分析

参考代码

最新文章

热门文章