非常细致的题解!!!
2026-10-07 14:49:35
发布于:北京
3阅读
0回复
0点赞
贪心策略:赚到自己能赚的钱、
1、如果田忌最快的马 比 齐王最快的马 快,田快 vs 王快,田忌得分
2、否则 如果田忌最快的马 比 齐王最快的马 慢,从这匹齐王最快的马上必失分,选择 田慢 vs 王快,尽量保存田有生力量
3、否则(田忌最快的马 和 齐王最快的马 同速)
3.1、如果 田忌最慢的马 比 齐王最慢的马 快,田慢 vs 王慢,田忌得分
3.2、否则 如果 田忌最慢的马 比 齐王最慢的马 慢,此时田慢参赛必失分,选择 田慢 vs 王快,尽量消耗王有生力量
3.3、否则(田忌最慢的马 和 齐王最慢的马 同速),选择 田慢 vs 王快,尽量消耗王有生力量
3.3.1、如果 田忌最慢的马 比 齐王最快的马 慢,田忌丢分
3.3.2、否则(田忌最慢的马 和 齐王最快的马 同速),此时继续赛马只有平局,田忌不会得分,也不会失分,赛马可以终止
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, a[1005], b[1005];
while(cin>>n) {
if(n==0) break;
for(int i=1; i<=n; i++) cin>>a[i]; //田忌
for(int i=1; i<=n; i++) cin>>b[i]; //齐王
sort(a+1, a+n+1);
sort(b+1, b+n+1);
//双指针 two-pointer
int i=n, j=n, ii=1, jj=1, sum=0;
while(i>=ii) {
if(a[i]>b[j]) { //田忌快马 比 齐王快马 快
//田快 vs 王快,田忌赢钱
sum+=200;
i--;
j--;
} else if(a[i]<b[j]) { //田忌快马 比 齐王快马 慢
//田慢 vs 王快,用最小代价消耗齐王最好战力
sum-=200;
ii++;
j--;
} else { //田忌快马 和 齐王快马 同速
if(a[ii]>b[jj]) { //田忌慢马 比 齐王慢马 快
//田慢 vs 王慢,田忌赢钱
sum+=200;
ii++;
jj++;
} else if(a[ii]<b[jj]) { //田忌慢马 比 齐王慢马 慢
//田慢 vs 王快,用最小代价消耗齐王最好战力
sum-=200;
ii++;
j--;
} else { //田忌慢马 和 齐王慢马 同速
//田慢 vs 王快, 用最小代价消耗齐王最好战力
if(a[ii]<b[j]) { //田慢 比 王快 慢,田失分
sum-=200;
ii++;
j--;
} else break; // 田慢 和 王快 同速,此后只有平局,循环可以结束
}
}
}
cout<<sum<<endl;
}
return 0;
}
这里空空如也







有帮助,赞一个