Asia Yokohama Regional Contest 2018 K

Desription

题目链接: https://codeforces.com/gym/102082/attachments

周末打训练赛时遇到的一道比较 interesting 的题目

题目大意是说有两个玩家 $a$ 和 $b$ 在比赛，$a$ 和 $b$ 各有 $n$ 张有一定数值的卡牌，在 $a$ 出牌方案固定的情况下，问 $b$ 如何调整出牌能使得 $b$ 获胜的次数最大，同时要让 $b$ 出牌方案的字典序最大. ( $1 \le n \le 5000$ )

Time Limit: $5$ $seconds$

Solution

如果不考虑出牌方案的字典序，这个题目就非常简单了

只需要将 $a$ 和 $b$ 的卡牌分别从小到大排序，每次从 $b$ 的卡牌中选出一张刚好大于 $a$ 所剩卡牌的最小值的卡牌，这样就可以使得 $b$ 的获胜场次最多. 因为数组已经排了序，可以用双指针来实现这一过程，并记这一最大值为 $ans$

下面需要考虑的就是如何最大化方案的字典序

我们首先考虑数组 $a_1,a_2,…,a_n$，当玩家 $a$ 出牌 $a_1$ 时，假如玩家 $b$ 想要赢下这一局，那么 $b$ 必须要出一张大小大于 $a_1$ 的牌，我们记这张牌为 $x$. 对于数组剩下的部分 ($a_2,a_3,…,a_n$) 和 ($b_1,b_2,…,b_n$-x)，通过我们上面的贪心策略必须要能达到 $ans-1$. 容易知道，我们选的这张牌 $x$ 越大，剩余部分越难能达到 $ans-1$. 我们可以二分这张大于 $a_1$ 的牌，找到剩余部分达到 $ans-1$ 的前提下，$x$ 最大能是多少. 假如此情况下无解，说明 $b$ 在这一局必须要输，我们同样可以二分这张小于等于 $a_1$ 的牌 $x$，找到剩余部分达到 $ans$ 的前提下，$x$ 最大能是多少.

总的时间复杂度为: $O(n^2logn)$

AC code

Time: 842ms

Memory: 200KB

#include <bits/stdc++.h>

using namespace std;

#define mem(a,i) memset(a,i,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;++i)
const int maxn=5005;
int n;
int a[maxn];
int b[maxn];
struct Node {
    int val,id;
    bool operator<(Node& e) const {
        if(val==e.val) return id<e.id;
        return val<e.val;
    }
} node[maxn];
bool mark[maxn];
bool vis[maxn];
int ta[maxn];
int tb[maxn];
int temp[maxn];
int m;
int out[maxn];

int solve() {
    if(m==0) return 0;
    int lb=1;
    int res=0;
    rep(i,1,m) {
        if(lb>m) break;
        while(lb<=m&&tb[lb]<=ta[i]) {
            lb++;
        }
        if(lb<=m) res++;
        lb++;
    }
    return res;
}

int main() {
    // freopen("in.txt","r",stdin);
    scanf("%d",&n);
    rep(i,1,n) {
        scanf("%d",&a[i]);
        node[i].id=i;
        node[i].val=a[i];
    }
    rep(i,1,n) scanf("%d",&b[i]);
    sort(node+1,node+1+n);
    sort(b+1,b+1+n);
    mem(mark,0);
    int lb=1;
    int ans=0;
    rep(i,1,n) {
        if(lb>n) break;
        while(lb<=n&&b[lb]<=node[i].val) {
            lb++;
        }
        if(lb<=n) {
            ans++;
        }
        lb++;
    }
    mem(vis,0);
    rep(i,1,n) {
        int k=0;
        rep(j,1,n) {
            if(!vis[j]) {
                temp[++k]=b[j];
            }
        }
        int o=0;
        rep(j,i+1,n) {
            ta[++o]=a[j];
        }
        sort(ta+1,ta+1+o);
        int pos=upper_bound(temp+1,temp+1+k,a[i])-temp;

        int l=pos,r=k;
        int id=-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            m=k-1;
            int o=0;
            rep(j,1,k) {
                if(j==mid) continue;
                tb[++o]=temp[j];
            }
            int res=solve();
            if(res+1==ans) {
                id=mid;
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }
        if(id!=-1) {
            assert(id!=-1);
            ans--;
            rep(j,1,n) {
                if(!vis[j]) {
                    if(b[j]==temp[id]) {
                        vis[j]=1;
                        out[i]=b[j];
                        break;
                    }
                }
            }
            continue;
        }

        l=1,r=pos-1;
        while(l<=r) {
            int mid=(l+r)>>1;
            m=k-1;
            int o=0;
            rep(j,1,k) {
                if(j==mid) continue;
                tb[++o]=temp[j];
            }
            int res=solve();
            if(res==ans) {
                id=mid;
                l=mid+1;
            }
            else {
                r=mid-1;
            }
        }
        assert(id!=-1);
        rep(j,1,n) {
            if(!vis[j]) {
                if(b[j]==temp[id]) {
                    vis[j]=1;
                    out[i]=b[j];
                    break;
                }
            }
        }

    }
    rep(i,1,n) printf("%d%c",out[i],i==n?'\n':' ');
    return 0;
}

贪心 + 二分

Desription

Solution

AC code

CATALOG

FEATURED TAGS

FRIENDS