题意:
两个人,各有N匹马,分别给出这2*n匹马的战力,两个人要对马,你知道对手的排序,求你最多可以赢几场?
题解:知识点:算个贪心吧。
就跟田忌赛马一样,你无非是找到比对手马略强一点的马来跟他的马比,这样才能应最多场。
把你和对手的马匹各自排序,从小到大,每次找比对手现在最小的马匹略大的马跟他比,这样你就赢一场,如果比最小的都小直接拉出去让他跟对手战力最大的马比。然后让后一个再跟这个最小的比。
代码:
#include <map> #include <queue> #include <string> #include<iostream> #include<stdio.h> #include<string.h> #include <algorithm> #include <math.h> typedef long long ll; using namespace std; typedef pair<ll,ll> pii; #define mem(a,x) memset(a,x,sizeof(a)) #define debug(x) cout << #x << ": " << x << endl; #define rep(i,n) for(int i=0;i<(n);++i) #define repi(i,a,b) for(int i=int(a);i<=(b);++i) #define repr(i,b,a) for(int i=int(b);i>=(a);--i) const int maxn=1e6+1010; #define inf 0x3f3f3f3f #define sf scanf #define pf printf const int mod=998244353; const int MOD=10007; inline int read() { int x=0; bool t=false; char ch=getchar(); while((ch<'0'||ch>'9')&&ch!='-')ch=getchar(); if(ch=='-')t=true,ch=getchar(); while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar(); return t?-x:x; } /*priority_queue<ll , vector<ll> , greater<ll> > mn;//上 小根堆 小到大 priority_queue<ll , vector<ll> , less<ll> > mx;//下 大根堆 大到小 map<ll,ll>mp;*/ ll n,m,t,l,r,p; ll sum,ans,res,cnt,flag,maxx,minn; bool isprime[maxn]; ll a[maxn],b[maxn],c[maxn]; ll dis[maxn],vis[maxn]; ll dp[1010][1010]; string str,s; #define read read() int main(){ t=read; while(t--){ n=read; for(int i=1;i<=n;i++) a[i]=read; for(int i=1;i<=n;i++) b[i]=read; sum=0; sort(a+1,a+1+n); sort(b+1,b+1+n); for(int i=1,j=1;i<=n;){ if(a[i]>b[j]){ i++; j++; sum++; }else i++; } cout<<sum<<endl; } return 0; }