CF1536D Omkar and Medians 题解

发布于 2021-06-08  236 次阅读


题意

题目链接

记 $b_i$ 为 $a_1 \sim a_{2i-1}$ 的中位数,给定序列 $b$,询问是否存在合法的序列 $a$。

解析

考虑 $b_i$ 和 $b_{i-1}$ 的关系。我们先假设 $b_1 \sim b_{i-1}$ 均合法。

  • 若 $b_{i-1}=b_i$,则新增的两个数只需一大一小地取即可,$b_i$ 也一定合法。
  • 若 $b_{i-1}<b_i$,因为 $b_{i-1}$ 是 $2i-3$ 个数的中位数,所以序列中一定有 $i-1$ 个数比 $b_i$ 小。对于任意一个 $b_j(j<i-1)$ ,如果其满足 $b_j \le b_{i-1}$,则它可以作为这 $i-1$ 个数中的一个数,不影响结果。若其满足 $b_{i-1} < b_j < b_i$,则此时我们发现序列中至少有 $i$ 个数比 $b_i$ 小,这就是不合法的。
  • 若 $b_{i-1}>b_i$,同理寻找有无一个 $b_j$ 满足 $b_{i-1}>b_j>b_i$ 即可。

我们发现所有相同的数出现一次和出现多次在统计答案时没有区别,因为可以简单地使用一个 set 维护,每次查询时:

  • 若 $b_{i-1}<b_i$,查询 $b_{i-1}$ 的后继是否为 $b_i$,若不是则不存在合法序列 $a$。
  • 若 $b_{i-1}>b_i$,查询 $b_i$ 的后继是否为 $b_{i-1}$。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int T,n;
int b[N];
set<int> s;
int main(){
    scanf("%d",&T);
    while(T--){
        bool fl=1;
        s.clear();
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            if(!s.count(b[i])) s.insert(b[i]);//相同的数无意义,直接不加入 set 即可。
            if(b[i]==b[i-1]) continue;
            if(b[i-1]<b[i]){
                if(s.upper_bound(b[i-1])!=s.find(b[i])){
                    fl=0;//若 b[i-1] 的后继不为 b[i],就不合法。
                }
            }
            else{
                if(s.upper_bound(b[i])!=s.find(b[i-1])){
                    fl=0;//同理
                }
            }
        }
        if(fl){
            printf("YES\n");
        }
        else{
            printf("NO\n");
        }
    }
    return 0;
}

月流华 岁遗沙 万古吴钩出玉匣