题目描述
分析：
经典贪心题，跟田忌赛马没什么区别。
1. 以最小的代价尽量多的赢
2. 尽量多的平局
3. 剩下的注定要输了。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 100000
int n,a[MAXN+],b[MAXN+],c[MAXN+],d[MAXN+];
int stak[MAXN+];
bool vis1[MAXN+],vis2[MAXN+];
int Greedy(int w[],int l[])
{
sort(l+,l+n+);
sort(w+,w+n+);
int ret=;
memset(vis1,,sizeof vis1);
memset(vis2,,sizeof vis2);
int top=,j=n;
for(int i=n;i>=;i--){
while(j>=&&w[j]>l[i])
stak[top++]=j--;
if(top>){
vis2[i]=true;
vis1[stak[top-]]=true;
top--;
ret+=;
}
}
int m=;
for(int i=;i<=n;i++){
if(!vis1[i])
c[++m]=w[i];
}
m=;
for(int i=;i<=n;i++){
if(!vis2[i])
d[++m]=l[i];
}
//此时最多打成平局
j=m,top=;
for(int i=m;i>=;i--){
while(j>=&&c[j]>=d[i])
stak[top++]=j--;
if(top>){
ret++;
top--;
}
}
return ret;
}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
scanf("%d",&b[i]);
printf("%d %d\n",Greedy(a,b),*n-Greedy(b,a));
}
转载于:https://www.cnblogs.com/katarinayuan/p/6572824.html