(題面來自洛谷)
題目描述
我國歷史上有個著名的故事： 那是在2300年以前，齊國的大將軍田忌喜歡賽馬，他經常和齊王賽馬，他和齊王都有三匹馬：常規馬，上級馬，超級馬，一共賽三局，每局的勝者可以從負者這里取得200銀幣，每匹馬只能用一次，齊王的馬好，同等級的馬，齊王的總是比田忌的要好一點，于是每次和齊王賽馬，田忌總會輸600銀幣，
田忌很沮喪，直到他遇到了著名的軍師――孫臏，田忌采用了孫臏的計策之后，三場比賽下來，輕松而優雅地贏了齊王200銀幣，這實在是個很簡單的計策，由于齊王總是先出最好的馬，再出次好的，所以田忌用常規馬對齊王的超級馬，用自己的超級馬對齊王的上級馬，用自己的上級馬對齊王的常規馬，以兩勝一負的戰績贏得200銀幣，實在很簡單，
如果不止三匹馬怎么辦？這個問題很顯然可以轉化成一個二分圖最佳匹配的問題，把田忌的馬放左邊，把齊王的馬放右邊，田忌的馬A和齊王的B之間，如果田忌的馬勝，則連一條權為200的邊；如果平局，則連一條權為0的邊；如果輸，則連一條權為－200的邊……如果你不會求最佳匹配，用最小費用最大流也可以啊， 然而，賽馬問題是一種特殊的二分圖最佳匹配的問題，上面的演算法過于先進了，簡直是殺雞用牛刀，現在，就請你設計一個簡單的演算法解決這個問題，
輸入格式
第一行一個整數n，表示他們各有幾匹馬（兩人擁有的馬的數目相同），第二行n個整數，每個整數都代表田忌的某匹馬的速度值(0 <= 速度值<= 100)，第三行n個整數，描述齊王的馬的速度值，兩馬相遇，根據速度值的大小就可以知道哪匹馬會勝出，如果速度值相同，則和局，誰也不拿錢，
【資料規模】
對于20%的資料，1<=N<=65；
對于40%的資料，1<=N<=250；
對于100%的資料，1<=N<=2000，
輸出格式
僅一行，一個整數，表示田忌最大能得到多少銀幣，
輸入輸出樣例
輸入 #1
3
92 83 71
95 87 74
輸出 #1
200
分析
代碼
// Problem: P1650 田忌賽馬
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1650
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using namespace std;
int n,
a[2001], //田忌的馬
b[2001], //齊王的馬
m1,
m2,
qian;
int main(){
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 n1=n-1,
n2=n-1;
while(m1<=n1){
if(a[n1]>b[n2]){ //田忌最快的比齊王最快的快
qian+=200; //贏錢
n1--,n2--; //兩邊各去掉一匹馬
}else if(a[n1]<b[n2]){//田忌最快的贏不了齊王最快的，就丟一匹最慢的
qian-=200; //輸錢
m1++,n2--;
}else{ //如果 勢 均 力 敵 的話
if(a[m1]>b[m2]){ //田忌最慢的能贏齊王最慢的，就上
qian+=200; //贏錢
m1++,m2++;
}else{ //贏不了就用最慢的消耗齊王最快的
if(a[m1]<b[n2]) qian-=200; //我 再 忍 你 一 手
m1++,n2--;
}
}
}
printf("%d",qian);
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/261228.html
標籤：C++