田忌赛马【洛谷P1650】

本文主要是介绍田忌赛马【洛谷P1650】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

P1650 田忌赛马 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include<iostream>
#include <algorithm>
#include<cstdio>
#include <map>
using namespace std;
const int N=1e5+100;
int n;
map<int,int>a,b;//映射，速度->数量
int maxa=-1,mina=N,maxb=-1,minb=N;
int cnt=0,res=0;
int main()
{cin>>n;for(int i=1;i<=n;i++)//田忌的马的速度{int x;cin>>x;maxa=max(maxa,x);//最大速度mina=min(mina,x);//最小速度a[x]++;//该速度的马的数量}for(int i=1;i<=n;i++)//齐王的马的速度{int x;cin>>x;maxb=max(maxb,x);//最大速度minb=min(minb,x);//最小速度b[x]++;//该速度的马的数量}//田忌会赢的for(int i=mina;i<=maxa;i++)//从田忌最小速度开始枚举到最大速度{cnt=a[i];//该速度的马的数量for(int j=1;j<=cnt;j++){for(int k=i-1;k>=minb;k--)//从齐王比田忌当前马速度慢的马的速度开始枚举到最小速度{if(b[k]>0)//齐王有此速度的马，田忌就赢一局{res+=200;a[i]--;b[k]--;//该数量的马都减1break;//找到就终止此次枚举}}}}//田忌会赢的已经枚举完，所以只剩平局和会输的for(int i=mina;i<=maxa;i++)//从田忌的马的最小速度开始枚举到最大速度{cnt=a[i];//该速度的马的数量for(int j=1;j<=cnt;j++){if(b[i]>0)//齐王也有该速度的马，平局{a[i]--;b[i]--;continue;}for(int k=maxb;k>0;k--)//田忌输的{if(b[k]>0){b[k]--;a[i]--;res-=200;break;}}}}cout<<res;return 0;
}

这篇关于田忌赛马【洛谷P1650】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---