1608C

2021-12-16

字数统计: 1.2k字 | 阅读时长≈ 5分

题目大意

有\(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\)~\(n\)个人中\(b\)能力值的最小值。

从后往前判断:

如果\(s[i][1] \le s[i-1][0]\),表明第\(i-1\)个人可以利用前面\(b\)能力值最大的人去击败\(i\)~\(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");
    }
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/12/16/CF1608C/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！