程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 【BZOJ1034】省隊選手不務正業打泡泡堂(我也不知道是啥算法),bzoj1034不務正業

【BZOJ1034】省隊選手不務正業打泡泡堂(我也不知道是啥算法),bzoj1034不務正業

編輯:C++入門知識

【BZOJ1034】省隊選手不務正業打泡泡堂(我也不知道是啥算法),bzoj1034不務正業


1034: [ZJOI2008]泡泡堂BNB


Description

  第XXXX屆NOI期間,為了加強各省選手之間的交流,組委會決定組織一場省際電子競技大賽,每一個省的代表
隊由n名選手組成,比賽的項目是老少鹹宜的網絡游戲泡泡堂。每一場比賽前,對陣雙方的教練向組委會提交一份
參賽選手的名單,決定了選手上場的順序,一經確定,不得修改。比賽中,雙方的一號選手,二號選手……,n號
選手捉對厮殺,共進行n場比賽。每勝一場比賽得2分,平一場得1分,輸一場不得分。最終將雙方的單場得分相加
得出總分,總分高的隊伍晉級(總分相同抽簽決定)。作為浙江隊的領隊,你已經在事先將各省所有選手的泡泡堂水
平了解的一清二楚,並將其用一個實力值來衡量。為簡化問題,我們假定選手在游戲中完全不受任何外界因素干擾
,即實力強的選手一定可以戰勝實力弱的選手,而兩個實力相同的選手一定會戰平。由於完全不知道對手會使用何
種策略來確定出場順序,所以所有的隊伍都采取了這樣一種策略,就是完全隨機決定出場順序。當然你不想這樣不
明不白的進行比賽。你想事先了解一下在最好與最壞的情況下,浙江隊最終分別能得到多少分。

Input

  輸入的第一行為一個整數n,表示每支代表隊的人數。接下來n行,每行一個整數,描述了n位浙江隊的選手的
實力值。接下來n行,每行一個整數,描述了你的對手的n位選手的實力值。 20%的數據中,1<=n<=10; 40%的數
據中,1<=n<=100; 60%的數據中,1<=n<=1000; 100%的數據中,1<=n<=100000,且所有選手的實力值在0到100
00000之間。

Output

  包括兩個用空格隔開的整數,分別表示浙江隊在最好與最壞的情況下分別能得多少分。不要在行末輸出多余的
空白字符。

Sample Input

2
1
3
2
4

Sample Output

2 0
 

樣例說明

我們分別稱4位選手為A,B,C,D。則可能出現以下4種對戰方式,最好情況下可得2分,最壞情況下得0分。
                      一                   二                     三                   四
              浙江 ??? 結果 浙江 ??? 結果 浙江 ??? 結果 浙江 ??? 結果
一號選手 A     C    負     A     D     負     B     C     勝     B      D     負
二號選手 B     D    負     B     C     勝     A     D     負     A      C     負
總得分            0                     2                    2                       0   這道題,一看就有很強的田忌賽馬即視感(實際上就是啊喂!)。 所以自然的就想到用貪心解決這道題。   至於我這個是不是一種算法我不是很清楚,但是我會一步步講清楚我的代碼,我要讓人人都能聽懂!  
 1 inline long long getans(long long *a,long long *b)
 2 {
 3     long long ans=0;
 4     int h=1,t=n;
 5     int h1=1,t1=n;
 6     while(h<=t)
 7     {
 8         if(a[h]>b[h1]) ans+=2,h++,h1++;
 9         else if(a[t]>b[t1]) ans+=2,t--,t1--;
10         else
11         {
12             if(a[h]==b[t1]) ans+=1;
13             h++,t1--;
14         }
15     }
16     return ans;
17 }
18  

這就是這道題的核心部分,當然,數據事先經過了排序。

整個過程就是找A方最弱的選手和B方最弱的選手比賽,如果打得過就打,打不過就去耗對面最強的人,贏了就+2分平局就+1分,然後記錄當前AB隊最弱最強的人,最後輸出答案就行了。

另外這道題還值得注意的一點是,我方最優勢的局就是對方最劣勢的局,也就是說第二問就是把對方當我方,讓對方打優勢,最後輸出答案的時候2*n-ans就行了。

 

最後提醒一句:不開long long見祖宗,十年OI一場空!

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved