列表

详情

NC200180. Sixth Sense

描述

Ms. Future is gifted with precognition. Naturally, she is excellent at some card games since she can correctly foresee every player’s actions, except her own. Today, she accepted a challenge from a reckless gambler Mr. Past. They agreed to play a simple two-player trick-taking card game.
Cards for the game have a number printed on one side, leaving the other side blank making indistinguishable from other cards.
A game starts with the same number, say n, of cards being handed out to both players, without revealing the printed number to the opponent.
A game consists of n tricks. In each trick, both players pull one card out of her/his hand. The player pulling out the card with the larger number takes this trick. Because Ms. Future is extremely good at this game, they have agreed to give tricks to Mr. Past when both pull out cards with the same number. Once a card is used, it can never be used later in the same game. The game continues until all the cards in the hands are used up. The objective of the game is to take as many tricks as possible.
Your mission of this problem is to help Ms. Future by providing a computer program to determine the best playing order of the cards in her hand. Since she has the sixth sense, your program can utilize information that is not available to ordinary people before the game

输入描述

The input consists of a single test case of the following format.
n 
p_1 ··· p_n 
f_1 ··· f_n 
n in the first line is the number of tricks, which is an integer between 2 and 5000, inclusive. The second line represents the Mr. Past’s playing order of the cards in his hand. In the i-th trick, he will pull out a card with the number p_i . The third line represents the Ms. Future’s hand. f_i  is the number that she will see on the i-th received card from the dealer. Every number in the second or third line is an integer between 1 and 10000, inclusive. These lines may have duplicate numbers.

输出描述

The output should be a single line containing n integers  separated by a space, where  is the number on the card she should play at the i-th trick for maximizing the number of taken tricks. If there are two or more such sequences of numbers, output the lexicographically greatest one among them.

示例1

输入: 

5 
1 2 3 4 5 
1 2 3 4 5

输出: 

2 3 4 5 1

示例2

输入: 

5 
3 4 5 6 7 
1 3 5 7 9

输出: 

9 5 7 3 1

示例3

输入: 

5 
3 2 2 1 1 
1 1 2 2 3

输出: 

1 3 1 2 2

示例4

输入: 

5 
3 4 10 4 9 
2 7 3 6 9

输出: 

9 7 3 6 2

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 890ms, 内存消耗: 484K, 提交时间: 2020-10-04 15:08:08 

#include<bits/stdc++.h>
#define REP(i,s,t) for(int i=s;i<=t;i++)
using namespace std;
int i,n,p[5005],f[5005],tmp[5005];
bool vis[5005];
int cal(int l,int cnt,int w)
{
    bool c[5005]= {0};
    c[w]=true;
    int ret=0,pt=1;
    REP(j,l,n)
    {
        while(pt<=n-i+1&&(c[pt]||tmp[j]>=f[pt])) pt++;
        if(pt<=n-i+1) ret++,c[pt]=true;
    }
    return ret;
}
int main()
{
    cin>>n;
    REP(i,1,n) cin>>p[i];
    REP(i,1,n) cin>>f[i];
    sort(f+1,f+1+n);
    memcpy(tmp,p,sizeof p);
    sort(tmp+1,tmp+1+n);
    int ans=cal(1,n,0),pre=0;
    for(i=1; i<=n; i++)
    {
        REP(j,i+1,n) tmp[j]=p[j];
        sort(tmp+i+1,tmp+1+n);
        int w=1;
        while(w<=n-i+1&&f[w]<=p[i]) w++;
        if(w<=n-i+1)
        {
            int l=w,r=n-i+1;
            while(l<=r)
            {
                int m=l+r>>1;
                if(pre+1+cal(i+1,n-i+1,m)==ans) l=m+1;
                else r=m-1;
            }
            if(f[r]>p[i])
            {
                cout<<f[r]<<' ';
                REP(j,r,n-i) f[j]=f[j+1];
                pre++;
                continue;
            }
        }
        int l=1,r=w-1;
        while(l<=r)
        {
            int m=l+r>>1;
            if(pre+cal(i+1,n-i+1,m)==ans) l=m+1;
            else r=m-1;
        }
        cout<<f[r]<<' ';
        REP(j,r,n-i) f[j]=f[j+1];
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 148ms, 内存消耗: 608K, 提交时间: 2020-10-08 21:57:18 

#include<bits/stdc++.h>
using namespace std;

const int N=10005;

int n,ans[N],l[N];
pair<int,int> a[N];
bool vis[N];

int main() {
	scanf("%d",&n);
	for (int i=1;i<=n;i++) {
		int x;
		scanf("%d",&x);
		a[i]={x,i};
	}
	for (int i=1;i<=n;i++) {
		int x;
		scanf("%d",&x);
		a[n+i]={x,-i};
	}
	sort(a+1,a+2*n+1);
	for (int i=1;i<=n;i++) {
		int cnt=0,lst=1;
		for (int j=1;j<=2*n;j++) if (!vis[j]) {
			if (a[j].second>0) {
				if (!cnt) lst=j;
				cnt++;
			}
			else {
				if (cnt) {
					l[j]=lst;
					cnt--;
				}
				else l[j]=0;
			}
		}
		for (int j=2*n;j;j--) if (!vis[j] && a[j].second<0) {
			int mx=1e9,pos=0;
			if (l[j]) {
				for (int p=l[j];p<j;p++) if (!vis[p] && a[p].second>0 && a[p].second<mx) mx=a[p].second,pos=p;
			}
			else {
				for (int p=1;p<=2*n;p++) if (!vis[p] && a[p].second>0 && a[p].second<mx) mx=a[p].second,pos=p;
			}
			vis[pos]=1;
			vis[j]=1;
			ans[a[pos].second]=a[j].first;
			break;
		}
	}
	for (int i=1;i<=n;i++) printf("%d%c",ans[i]," \n"[i==n]);
}

上一题

© 2024 nowcoder.com