【CodeForces】1608C Game Master题解

题目大意

有 $n$ 个人比赛，每个人有 $a, b$ 两个能力值。

比赛由你组织，你可以任意挑选两个人，并且挑选他们任意的能力值来让他们比赛。能力值大的一方将会胜出，而输掉的那个人将会被淘汰。（也就是说，经过 $n-1$ 次比赛后，将会决出胜者）。每个人的 $a$ 能力值各不相同，$b$ 能力值各不相同。

现在请问，每个人是否有可能可以胜出呢？可以输出 $1$，不可以输出 $0$。

原题地址

分析

我们容易想到这么一种情况：$x$ 的 $a, b$ 能力值都不是很高，但是有个 $y$，它的能力值一个非常高，一个非常低，且刚好低于 $x$ 相对较高的能力值。

那么我们可以先让 $y$ 用高的能力值把其它所有人都打败，然后再让 $x$ 用较高的能力值打败用低能力值的 $y$。（偷偷吃鸡是吧）

当然也有可能 $x$ 实在是太菜了，以至于它连 $y$ 的低能力值也打不过。

思路

我们再往下分析，假设 $x$ 能打败 $y$，那么 $x$ 能”打败”的最高对手就是 ${x, y}$ 中能力值最高的人能打败的对手，并且这种关系是可以传递的。比如又来了一个 $z$，它可以被 $y$ 击败，尽管 $x$ 可能打不过 $z$，但是凭借 $y$，那么 $x$ 依然有可能是冠军。

但是同时处理 $a, b$ 两种能力值有些困难，所以我们不妨先按照 $a$ 能力值大小升序排序，那么在后面的人始终可以凭借 $a$ 能力值去击败前面的。

首先 $a$ 能力值最高的人是肯定可以胜出的，所以我们从后往前，依次判断这个人是否可能胜出。

如果这个人可以”击败”的人中能力的最大值大于 $a$ 能力最高的人的能力最低值，那么他也可以”胜出”。

那么前面的人就只能靠 $b$ 能力值去击败后面的人，注意我们不是要真正的打败后面的，而是胜出，即利用我们前面说的传递关系。

下面就是解决本题的最重要的结论：

• 假如第 $n-1$ 个人可以胜出，那么第 $n-2$ 个人才有可能胜出。因为第 $n-1$ 个人可以击败除了第 $n$ 个人之外的所有人，并且利用它们的能力值，也无法击败第 $n$ 个人，那么第 $n-2$ 个人也铁定无法击败 $n$。

• 如果 $n-1, n-2$ 都可以胜出，那么 $n-3$ 只需要击败 $n, n-1, n-2$ 中任意一个人，就能够胜出。

  证明：假设击败的这个人是 $x$，那么 $x$ 胜出时，要么是利用了 $n-3$ 击败了其他人，要么没有利用 $n-3$：

  • 利用了 $n-3$，说明 $n-3$ 本来就可以胜出，那么本身就可以胜出。
  • 没有利用 $n-3$，那么我们可以先让 $x$ 把其它所有人都”击败”，然后再让 $n-3$ 把 $x$ 击败。

做法

按照 $a$ 能力值排序后，

我们用 $s[i][0]$ 记录前 $i$ 个人中 $b$ 能力值的最大值，$s[i][1]$ 记录 $i \sim n$ 个人中 $b$ 能力值的最小值。

从后往前判断：

如果 $s[i][1] \le s[i-1][0]$，表明第 $i-1$ 个人可以利用前面 $b$ 能力值最大的人去击败 $i \sim n$ 中 $b$ 能力值最小的那个人，所以可以胜出。

而如果 $s[i][1] > s[i-1][0]$，表明 $i-1$ 无法利用前面的人去击败任何一个后面的人，那么 $1$ 到 $i-1$ 中的人也就无法胜出。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;

const int maxN = 1e6 + 7;
const long long INF = 0x7f7f7f7f;

int T, n, ans[maxN];
long long s[maxN][2];

struct Num {
    long long x, y;
    int id;
}a[maxN];

bool cmp(Num a, Num b)
{
    return a.x < b.x;
}

int main()
{
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; ++i)
            a[i].id = i;
        for(int i = 1; i <= n; ++i)
            scanf("%lld", &a[i].x);
        for(int i = 1; i <= n; ++i)
            scanf("%lld", &a[i].y);
        sort(a + 1, a + 1 + n, cmp);
        int pos = 0;
        s[n + 1][1] = INF;
        for(int i = 1; i <= n; ++i)
            s[i][0] = max(s[i - 1][0], a[i].y);
        for(int i = n; i >= 1; --i)
            s[i][1] = min(s[i + 1][1], a[i].y);
        for(int i = n; i >= 1; --i)
            if(s[i][1] > s[i - 1][0]) {
                pos = i;
                break;
            }
        for(int i = 1; i < pos; ++i)
            ans[a[i].id] = 0;
        for(int i = pos; i <= n; ++i)  
            ans[a[i].id] = 1;
        for(int i = 1; i <= n; ++i)
            printf("%d", ans[i]);
        printf("\n");
    }
}