https://www.luogu.org/problem/P1650
題目描述
我國歷史上有個(gè)著名的故事： 那是在2300年以前。齊國的大將軍田忌喜歡賽馬。他經(jīng)常和齊王賽馬。他和齊王都有三匹馬：常規(guī)馬，上級(jí)馬，超級(jí)馬。一共賽三局，每局的勝者可以從負(fù)者這里取得200銀幣。每匹馬只能用一次。齊王的馬好，同等級(jí)的馬，齊王的總是比田忌的要好一點(diǎn)。于是每次和齊王賽馬，田忌總會(huì)輸600銀幣。

田忌很沮喪，直到他遇到了著名的軍師――孫臏。田忌采用了孫臏的計(jì)策之后，三場(chǎng)比賽下來，輕松而優(yōu)雅地贏了齊王200銀幣。這實(shí)在是個(gè)很簡單的計(jì)策。由于齊王總是先出最好的馬，再出次好的，所以田忌用常規(guī)馬對(duì)齊王的超級(jí)馬，用自己的超級(jí)馬對(duì)齊王的上級(jí)馬，用自己的上級(jí)馬對(duì)齊王的常規(guī)馬，以兩勝一負(fù)的戰(zhàn)績贏得200銀幣。實(shí)在很簡單。

如果不止三匹馬怎么辦？這個(gè)問題很顯然可以轉(zhuǎn)化成一個(gè)二分圖最佳匹配的問題。把田忌的馬放左邊，把齊王的馬放右邊。田忌的馬A和齊王的B之間，如果田忌的馬勝，則連一條權(quán)為200的邊；如果平局，則連一條權(quán)為0的邊；如果輸，則連一條權(quán)為－200的邊……如果你不會(huì)求最佳匹配，用最小費(fèi)用最大流也可以啊。 然而，賽馬問題是一種特殊的二分圖最佳匹配的問題，上面的算法過于先進(jìn)了，簡直是殺雞用牛刀。現(xiàn)在，就請(qǐng)你設(shè)計(jì)一個(gè)簡單的算法解決這個(gè)問題。

輸入格式
第一行一個(gè)整數(shù)n，表示他們各有幾匹馬（兩人擁有的馬的數(shù)目相同）。第二行n個(gè)整數(shù)，每個(gè)整數(shù)都代表田忌的某匹馬的速度值(0 <= 速度值<= 100)。第三行n個(gè)整數(shù)，描述齊王的馬的速度值。兩馬相遇，根據(jù)速度值的大小就可以知道哪匹馬會(huì)勝出。如果速度值相同，則和局，誰也不拿錢。

【數(shù)據(jù)規(guī)模】

對(duì)于20%的數(shù)據(jù)，1<=N<=65；

對(duì)于40%的數(shù)據(jù)，1<=N<=250；

對(duì)于100%的數(shù)據(jù)，1<=N<=2000。

輸出格式
僅一行，一個(gè)整數(shù)，表示田忌最大能得到多少銀幣。

輸入輸出樣例
輸入 #1 復(fù)制

3 92 83 71 95 87 74

輸出 #1 復(fù)制

200

AC_code:

#include <bits/stdc++.h> using namespace std; const int MAXN = 2e3+10; int a[MAXN]; int b[MAXN]; int main() {int n;while(~scanf("%d",&n)){for(int i = 0; i < n; i++){scanf("%d",&a[i]);}for(int i = 0; i < n; i++){scanf("%d",&b[i]);}sort(a,a+n);sort(b,b+n);int i = 0,j = n-1;int t = 0,k = n-1,cnt = 0;//cnt記錄比的次數(shù)int x = 0, y = 0;//x--〉vectory,y--->defeatwhile(cnt < n){if(a[j] > b[k])//后面直接大于先比掉{x++;j--;k--;cnt++;}else{while(a[i] > b[t] && cnt < n)//前面直接大于也先比掉{x++;i++;t++;cnt++;}if(cnt == n) break;if(a[i] < b[k]) y++; //此時(shí)小的也比不過誰了，所以用小的來消耗大的i++;k--;cnt++;}if( j < 0|| k < 0) break;//防越界吶！！}//cout<<x<<" "<<y<<endl;printf("%d\n",(x-y)*200);}return 0; } /* 3 2 4 4 2 3 3 3 2 3 5 1 2 5 3 2 3 5 2 2 5 */

總結(jié)

以上是生活随笔為你收集整理的P1650 田忌赛马（贪心）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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