洛谷——P2587 [ZJOI2008]泡泡堂

?兩隊(duì)人馬進(jìn)行比賽, 戰(zhàn)斗力值各有差異, 如果一方獲勝得兩分，戰(zhàn)平各得一分，失敗不得分，求可取得的最佳戰(zhàn)績與最差戰(zhàn)績。

? ? ? ? 思路：1）最強(qiáng)的打得過最強(qiáng)的就直接上；

? ? ? ? ? ? ? ? ?? 2）最弱的打得過最弱的直接上；

? ? ? ? ? ? ? ? ?? 3）我方最弱的打不過對(duì)方最弱的，送人頭消耗對(duì)方最強(qiáng)的兵。這樣我方就有效保留了一位戰(zhàn)力強(qiáng)的兵。為什么是有效，因?yàn)橐呀?jīng)打不過了，打最弱是掛，打最強(qiáng)也是掛呀，弱者也要死得其所。。。如果此時(shí)是打平呢?分析下得失，如果送人頭消耗了最強(qiáng)的兵，則我方最強(qiáng)的兵至少對(duì)戰(zhàn)最弱的兵可以獲勝，這就更有優(yōu)勢(shì)；比如1,4與1,4；打平不如打消耗。

1 #include<iostream> 2 #include<algorithm> 3 using namespace std; 4 const int MAX=100001; 5 int fight(int a[],int b[],int n,bool high); 6 7 int main() 8 { 9 int a[MAX],b[MAX]; 10 int n; 11 cin>>n; 12 for(int i=0;i<n;i++) cin>>a[i]; 13 for(int i=0;i<n;i++) cin>>b[i]; 14 sort(a,a+n); 15 sort(b,b+n); 16 cout<<fight(a,b,n,true)<<" "<<fight(b,a,n,false)<<endl; //反復(fù)提交n次發(fā)現(xiàn)不要求分行,mmm 17 18 return 0; 19 } 20 21 int fight(int a[],int b[],int n,bool high) 22 { 23 int iLeft,iRight,jLeft,jRight,win; 24 iLeft=jLeft=0; 25 win=0; 26 iRight=jRight=n-1; 27 while(iLeft<=iRight&&jLeft<=jRight) 28 { 29 if(a[iRight]>b[jRight]) 30 { 31 win+=2; 32 iRight--; 33 jRight--; 34 } 35 else if(a[iLeft]>b[jLeft]) 36 { 37 win+=2; 38 iLeft++; 39 jLeft++; 40 } 41 else if(a[iLeft]==b[jRight]) //相等則說明剩下的數(shù)都是相等的，即打平 42 { 43 win+=(iRight-iLeft+1); 44 break; 45 } 46 else 47 { 48 iLeft++; 49 jRight--; 50 } 51 } 52 if(high) return win; //如果high為真，求a隊(duì)最高分 53 else return (2*n-win); //如果high為假，求a隊(duì)最低分，此時(shí)b隊(duì)得分最高，總分為2*n 54 }

?

提交了n遍就是不過，出現(xiàn)Wrong Answer Too short on line 1，后來對(duì)比別人的才發(fā)現(xiàn)輸出時(shí)換行導(dǎo)致與要求格式不同。

小結(jié)：

1、提交前先上IDE確認(rèn)能否通過；

2、不要盲目提交，分析原因 ( 比對(duì)結(jié)果格式/題目要求，分析對(duì)比他人結(jié)果）；

3、方法總比問題多，放空思緒, 歇會(huì)再來。

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

總結(jié)

以上是生活随笔為你收集整理的每日一练之贪心算法(P2587)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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