題目鏈接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5158

題目大意：

??? 敵我雙方，我方n只軍隊(duì)，敵方m只軍隊(duì)，每只軍隊(duì)兩個(gè)屬性值，生命值和攻擊力。兩軍交戰(zhàn)，本身生命值減去對(duì)方的攻擊力。若剩余生命值小于等于0，則犧牲。問我軍能否消滅敵軍，能的話，最多生還多少隊(duì)伍，不能的話，輸出-1。

解題：

??? 做的時(shí)候，怎么都理不清思路，因?yàn)橐Y(jié)合數(shù)據(jù)結(jié)構(gòu)考慮，始終覺得無法找到合適的數(shù)據(jù)結(jié)構(gòu)。參考了這篇博客，大致思路是這樣的，首要任務(wù)是消滅全部敵軍，次要任務(wù)是保全更多的自己的部隊(duì)。先將我方軍隊(duì)按攻擊力排序，敵方軍隊(duì)按生命值排序。用multiset維護(hù)我方軍隊(duì)的生命值，只要加入multiset中的軍隊(duì)，其攻擊力都是足以消滅敵方的當(dāng)前和以后的隊(duì)伍的。對(duì)于敵方的一只軍隊(duì)，找到我方中，能消滅他的，且不被他消滅的最小生命值，倘若不存在，則犧牲multiset中最小的那個(gè)值。

總結(jié)：

??? 對(duì)于貪心問題，要明確貪心策略，理清思路，才能有助于解題。

補(bǔ)充：

??? 另外multiset的使用也需小心，erase操作，對(duì)應(yīng)兩種參數(shù)，如果是一個(gè)數(shù)值的話，那刪除的是所有該數(shù)值的值，如果是一個(gè)迭代器，那只刪除該迭代器對(duì)應(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);
		//如果我方軍隊(duì)數(shù)量小于敵方，直接輸出-1
		if(n<m)
		{
			printf("-1n");
			continue;
		}
		//我方按攻擊力高排序
		sort(us,us+n,cmp1);
		//敵方按生命值排序
		sort(en,en+m,cmp2);
		//存儲(chǔ)我方的攻擊力
		multiset?defense;
		//p我方下標(biāo)，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;
			}
			//如果我方剩余軍隊(duì)不能消滅敵方隊(duì)伍，break，輸出-1
			if(defense.empty())
			{
				flag=false;
				break;
			}
			else
			{
			???//能不損失軍隊(duì)，則用我方生命值恰好高于敵方的去消滅
			???//倘若必須損失軍隊(duì)，則損失當(dāng)前生命值最低的
			???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;
}