題目鏈接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5158
題目大意:
??? 敵我雙方,我方n只軍隊,敵方m只軍隊,每只軍隊兩個屬性值,生命值和攻擊力。兩軍交戰(zhàn),本身生命值減去對方的攻擊力。若剩余生命值小于等于0,則犧牲。問我軍能否消滅敵軍,能的話,最多生還多少隊伍,不能的話,輸出-1。
解題:
??? 做的時候,怎么都理不清思路,因為要結(jié)合數(shù)據(jù)結(jié)構(gòu)考慮,始終覺得無法找到合適的數(shù)據(jù)結(jié)構(gòu)。參考了這篇博客,大致思路是這樣的,首要任務(wù)是消滅全部敵軍,次要任務(wù)是保全更多的自己的部隊。先將我方軍隊按攻擊力排序,敵方軍隊按生命值排序。用multiset維護我方軍隊的生命值,只要加入multiset中的軍隊,其攻擊力都是足以消滅敵方的當前和以后的隊伍的。對于敵方的一只軍隊,找到我方中,能消滅他的,且不被他消滅的最小生命值,倘若不存在,則犧牲multiset中最小的那個值。
總結(jié):
??? 對于貪心問題,要明確貪心策略,理清思路,才能有助于解題。
補充:
??? 另外multiset的使用也需小心,erase操作,對應(yīng)兩種參數(shù),如果是一個數(shù)值的話,那刪除的是所有該數(shù)值的值,如果是一個迭代器,那只刪除該迭代器對應(yīng)的值。詳見此博客。
代碼:
#include#include#include#include#includeusing?namespace?std; struct?troop { //傷害,生命值 int?harm,life; }us[100010],en[100010]; //按攻擊力排序 bool?cmp1(troop?a,troop?b) { return?a.harm>b.harm; } //按生命值排序 bool?cmp2(troop?a,troop?b) { return?a.life>b.life; } int?main() { int?t,p=0,cnt,n,m; bool?flag; scanf("%d",&t); for(int?i=1;i<=t;i++) { printf("Case?#%d:?",i); scanf("%d%d",&n,&m); ????????for(int?j=0;j<n;j++) scanf("%d%d",&us[j].harm,&us[j].life); for(int?j=0;j<m;j++) scanf("%d%d",&en[j].harm,&en[j].life); //如果我方軍隊數(shù)量小于敵方,直接輸出-1 if(n<m) { printf("-1n"); continue; } //我方按攻擊力高排序 sort(us,us+n,cmp1); //敵方按生命值排序 sort(en,en+m,cmp2); //存儲我方的攻擊力 multiset?defense; //p我方下標,cnt我方犧牲數(shù)量 p=cnt=0; flag=true; ????????for(int?j=0;j<m;j++) { for(int?k=p;k=en[j].life) { defense.insert(us[k].life); p++; } else?break; } //如果我方剩余軍隊不能消滅敵方隊伍,break,輸出-1 if(defense.empty()) { flag=false; break; } else { ???//能不損失軍隊,則用我方生命值恰好高于敵方的去消滅 ???//倘若必須損失軍隊,則損失當前生命值最低的 ???multiset::iterator?it; ???????????????it=defense.upper_bound(en[j].harm); ???if(it!=defense.end()) ???defense.erase(it); ???else ???{ ???defense.erase(defense.begin()); ???cnt++; ???} } } if(!flag) printf("-1n"); else? printf("%dn",n-cnt); } return?0; }