當前位置:首頁 > 芯聞號 > 充電吧
[導(dǎo)讀]題目鏈接:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_

題目鏈接: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;
}




本站聲明: 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險,如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉