題目描述

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

輸入

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

輸出

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

樣例輸入

2
1
3
2
4

樣例輸出

2 0

---

題解

花式貪心

這道題類似于田忌賽馬的原理，但是有平的情況，需要另加處理。

首先，如果我方最弱能打敗對方最弱，那么肯定要打。

? ? ? ? ?如果我方最強能打敗對方最強，那么肯定要打。

然后就是平局的情況。

考慮：如果自己放棄平局的機會，讓給更強的人去打對方最弱，可能會更合適。

這前提是我方更強的人打不過對方其他人。

于是可以總結出：

? ? 1.如果我方最弱能打敗對方最弱，那么肯定要打（貪心）

? ? 2.如果我方最強能打敗對方最強，那么肯定要打（貪心）

? ? 3.如果都不能，那么讓我方最弱去打對方最強，結果未知（花式貪心）

可能這么說不太好理解，通過一組數據：3 ?1 2 5 ?1 3 4 ，能夠更深刻地理解貪心法則。

這是最優情況。由于兩方分數和為2n，我方最差情況即為對方最優情況，所以反過來再算一遍即可。

#include <cstdio> #include <algorithm> using namespace std; int a[100001] , b[100001]; int solve(int *a , int *b , int n) {int i = 1 , j = 1 , k = n , l = n , ans = 0;while(i <= k){if(a[i] > b[j]) ans += 2 , i ++ , j ++ ;else if(a[k] > b[l]) ans += 2 , k -- , l -- ;else ans += (a[i] == b[l]) , i ++ , l -- ;}return ans; } int main() {int n , i;scanf("%d" , &n);for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &a[i]);for(i = 1 ; i <= n ; i ++ ) scanf("%d" , &b[i]);sort(a + 1 , a + n + 1);sort(b + 1 , b + n + 1);printf("%d %d\n" , solve(a , b , n) , 2 * n - solve(b , a , n));return 0; }

轉載于:https://www.cnblogs.com/GXZlegend/p/6398166.html

總結

以上是生活随笔為你收集整理的【bzoj1034】[ZJOI2008]泡泡堂BNB 贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。