1118 AlvinZH's Fight with DDLs II

思路

中等題，貪心。

理解題意，每次攻擊中，可以使某個敵人生命值-1，自己生命值減去∑存活敵人總攻擊力。

貪心思想，血量少攻擊高的要先消滅，所以以A/L作為參數(shù)排序，即將所有的敵人根據(jù)A/L從大到小排序。

遍歷一次，對于排序好的敵人，HP減去（總攻擊*該敵人血量），總攻擊減去該敵人攻擊。代碼如下：

HP -= (sumA * H[i].L); sumA -= H[i].A; if(HP <= 0) break;

分析

貪心證明：對于已經(jīng)排好序的序列，HP總消耗為 \(\sum_{i = 1}^{n}\sum_{j = i}^{n}\left ( H[i].L*H[j].A \right )\) 。

如果我們交換其中相鄰兩個的位置，位置設(shè)為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\) ，而現(xiàn)在變成了\(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的。

由此可以證明：如果相鄰兩個交換，會導(dǎo)致HP總消耗增加。任何的一個攻擊敵人次序，都可以在已排好序的次序上通過多次上述交換（相鄰，且索引值小的后移）得到，由此可以判斷所有的攻擊次序HP消耗值都大于等于原排序攻擊次列。

貪心得證，至于如何多次交換，可參考冒泡排序過程。

時間復(fù)雜度：O(nlgn)。

空間復(fù)雜度：O(n)。

參考代碼

/* Author: 朱輝(35)Result: AC Submission_id: 514527Created 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");} }

轉(zhuǎn)載于:https://www.cnblogs.com/AlvinZH/p/8215853.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的2016级算法期末上机-F.中等·AlvinZH's Fight with DDLs II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。