田忌赛马

xiaoxiao2021-02-28  12

原题:1342–赛马–中级

题意:

如田忌赛马,求田忌通过这n匹马可以赢的场数的最大值

解析:

sort一遍,先比较最小的,如果最小的马之间田忌可以赢一场,那么就比掉;然后同样的道理比最大的;如果还不行的话,再拿田忌的弱鸡马消耗掉王的宝马(当然排除掉相同的情况才能消耗)。

其实这道题有很多其他的方法也可以求,但是要小心别错在了相同的情况。

当然了,这个方法应该是最优的,不管是时间还是空间

代码:

#include<iostream> #include<cstdio> #include<cmath> #include<string> #include<cstring> #include<algorithm> #include<set> #include<map> #include<list> #include<vector> #include<stack> #include<queue> #include<ctime> #include<cstdlib> #include<sstream> //#include<windows.h> #include<functional> #define D long long #define F double #define MAX 0x7fffffff #define MIN -0x7fffffff #define mmm(a,b) memset(a,b,sizeof(a)) #define pb push_back #define mk make_pair #define fi first #define se second #define pill pair<int, int> #define for1(i,a,b) for(int i=a;i<=b;i++) #define for2(i,a,b) for(int i=a;i>=b;i--) #define ini(n) scanf("%d",&n) #define inll(n) scanf("%lld",&n) #define outisp(n) printf("%d ",n) #define outllsp(n) printf("%lld ",n) #define outiel(n) printf("%d\n",n) #define outllel(n) printf("%lld\n",n) using namespace std; #define N 500100 #define MOD ((int)1e9+7) #define random(a,b) (rand()%(b-a+1)+a) #define stop Sleep(2000) #define CLS system("cls") const string el="\n"; const string elel="\n\n"; const string sp=" "; const string spsp=" "; const string tab="\t"; int king[6000],tian[6000]; int sum=0; int main(){ int n;ini(n); for1(i,1,n)ini(king[i]); for1(i,1,n)ini(tian[i]); sort(king+1,king+1+n);sort(tian+1,tian+1+n); int ki=1,kj=n,ti=1,tj=n; for1(ijk,1,n){ if(tian[ti]>king[ki]){ ti++;ki++;sum++; } else if(tian[tj]>king[kj]){ tj--;kj--;sum++; } else if(tian[ti]<king[kj]){ ti++;kj--;sum--; } } outiel(sum); }
转载请注明原文地址: https://www.6miu.com/read-1600353.html

最新回复(0)