6387. 【NOIP2019模拟2019.10.26】小w与卡牌游戏
Description
在昨天玩了数字游戏后，小w觉得不过瘾，叫上了小c一起来玩卡牌游戏。
小w和小c各有n张扑克牌，每张牌上都有一个数字。游戏共进行n轮，每轮两人各会出一张扑克牌。对于每一轮，牌面上数字大的人获胜并获得一分。鉴于小w是卡牌高手，所以他会让着小c。因此如果两张牌面的数字相同，则小c获胜。
小w之所以能成为卡牌高手，是因为它有很强的第六感。他可以通过心灵感应获取了小c手上所有卡牌上的数字以及小c的出牌顺序。通过这些信息，小w可以安排自己的出牌顺序以获得尽量多的分数。
小w把这个任务交给了你，他想要知道一种出牌顺序，使得它的得分最多。特别地，如果有多种合法的出牌顺序，他希望出牌顺序的字典序最大。
Input
第一行一个整数n，表示游戏的轮数。
第二行n个整数，表示小c手上的卡牌ci，卡牌按出牌顺序依次给出。
第三行n个整数，表示小w手上的卡牌wi。
Output
n个整数，表示得分最高且字典序最大的出牌顺序。
Sample Input
【输入样例1】
5
1 2 3 4 5
1 2 3 4 5
【输入样例2】
5
3 4 5 6 7
1 3 5 7 9
Sample Output
【输出样例1】
2 3 4 5 1
【输出样例2】
9 5 7 3 1
Data Constraint
对于30%的数据，n<=10
对于另外20%的数据，数据保证只存在一种使小w得分最高的方案
对于100%的数据，n<=1000
数据保证1<=ci,wi<=10^9
Hint
对于第一组样例，小w可以赢得前四局（2>1,3>2,4>3,5>4），输掉最后一局。
注意如果小w按1,2,3,4,5的顺序出牌，他会输掉所有比赛。
对于第二组样例，小w可以赢得前三局。可以证明这是赢得三局的情况下字典序最大的出牌顺序。
Solution
如果没有字典序最大的要求，那么我们可以贪心地解决这个问题。将小c的牌和小w的牌都排序，从大到小考虑w的牌，对于c的每张牌，尽量用最小的w的比这张牌大的牌，如果没有则跳过。如果只有一种合法方案，这种做法可以获得最优解。
时间复杂度O(nlogn)，期望得分20，结合枚举所有情况期望得分50。
正解是我们先求出小w的最高得分，然后再解决字典序最大这个要求。对于这个要求，我们可以从前往后一位一位贪心的解决。对于每一位，我们贪心地选择在不影响最高得分的情况下数字最大的牌。这个问题可以通过二分答案再贪心判定解决。对于每一位先二分这位填什么数字，但是要注意二分的时候要将w的牌分为两类，一类是大于a[i]的，由于对答案的贡献都是1,所以当w的牌越大的时候，对后面的出牌就越不优，再结合字典序最大的条件，我们因在合法时将指针向w的更大的牌移，而不合法时向更小的w的牌移；而对于小于等于a[i]的，由于贡献都为0，同样当w越大的时候，对后面出牌越不优。最后对于这个位置之后的其他牌用贪心判定即可。
时间复杂度O(n^2*logn)，期望得分100。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define I int
#define ll long long
#define F(i,a,b) for(I i=a;i<=b;++i)
#define Fd(i,a,b) for(I i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
#define N 1010
using namespace std;
I rd(I &x){
x=0;I w=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-') w=-1;c=getchar();}
while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
x*=w;
}
I n,a[N],b[N],c[N],d[N],t,s,l,r,k,mid,ans,tot;
I cmp(I x,I y){return x>y;}
I check(I x,I y){
I k=0,p=0;
F(i,1,s){
if(k+1==x) k++;
if(k<s&&b[k+1]>c[i]) k++,p++;
}
return p+tot+y==t;
}
I main(){
freopen("card.in","r",stdin);
freopen("card.out","w",stdout);
scanf("%d",&n);
F(i,1,n){scanf("%d",&a[i]),c[i]=-a[i];}
sort(c+1,c+1+n);
F(i,1,n) scanf("%d",&b[i]),c[i]=-c[i];
sort(b+1,b+1+n,cmp);
F(i,1,n) if(t<n&&b[t+1]>c[i]) t++;
s=n+1;
F(i,1,n-1){
s--;
F(j,1,s) if(c[j]==a[i]){c[j]=1e9;break;}
I k=s+1;
F(j,1,s) if(b[j]<=a[i]){k=j;break;}
l=1,r=k-1,ans=0;
while(l<=r){
mid=(l+r)>>1;
if(check(mid,1)){ans=mid,r=mid-1;}
else l=mid+1;
}
if(!ans){
l=k,r=s;
while(l<=r){
mid=(l+r)>>1;
if(check(mid,0)){ans=mid,r=mid-1;}
else l=mid+1;
}
}
printf("%d ",b[ans]);
tot+=(b[ans]>a[i]);
F(j,ans,s-1) b[j]=b[j+1];
F(j,1,s) if(c[j]==1e9){
F(k,j,s-1) c[k]=c[k+1];
break;
}
}
printf("%d ",b[1]);
return 0;
}作者：zsjzliziyang
QQ:1634151125
转载及修改请注明
本文地址:https://blog.csdn.net/zsjzliziyang/article/details/102788954