CF1349B Orac and Medians 题解

题目链接：CF1349B Orac and Medians

题意：

Slime 有一个正整数序列 $a_1, a_2, \ldots, a_n$。

在一次操作中，Orac可以选择这个序列的任意子段 $[l \ldots r]$ 并将 $a_l, a_{l+1}, \ldots, a_r$ 的所有值替换为 ${a_l, a_{l+1}, \ldots, a_r}$ 的中位数。

在这个问题中，对于整数多重集 $s$，$s$ 的中位数等于其中第 $\lfloor \frac{|s|+1}{2}\rfloor$ 小的数字。例如，${1,4,4,6,5}$ 的中位数是 $4$，${1,7,5,8}$ 的中位数是 $5$。

Slime 希望 Orac 通过这些操作使得 $a_1 = a_2 = \ldots = a_n = k$。

Orac 认为这是不可能的，他不想浪费时间，所以决定问你是否有可能满足 Slime 的要求，他可能会多次问这个问题。

输入格式：

输入的第一行是一个整数 $t$，表示查询的次数。

每个查询的第一行包含两个整数 $n\ (1\le n\le 100,000)$ 和 $k\ (1\le k\le 10^9)$，第二行包含 $n$ 个正整数 $a_1,a_2,\dots,a_n\ (1\le a_i\le 10^9)$。

$n$ 的总和最多为 $100,000$。

输出格式：

输出应包含 $t$ 行。第 $i$ 行应等于 yes，如果可以通过一些操作使得所有整数都等于 $k$，否则为 no。

你可以将每个字母都打印为小写或大写。

一道结论题，直接给结论了，

• $k \not\in a$ 则必定无解。
• 相邻的三个数中只要存在任意两个相等，则将它们进行操作后，均会变为那个相等的数
• 相邻的两个数进行操作后会变为较小的那个数。

由上面的若干结论可推出以下结论

• 如果有两个相邻的数都大于 $k$ ，则一定有解。
• 如果有两个间隔为 $1$ 的数都大于 $k$ ，记为 $a_i$ 和 $a_{i+2}$ ，则对 $[i,~i+2]$ 操作一次即可转为上一种情况。

时间复杂度 $\mathcal{O}(\sum n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(1e5 + 15))

int a[N];
void solve()
{
    int n,k; cin >> n >> k; char ok = 0;
    for(int i = 1; i <= n; i++) { cin >> a[i]; ok |= (a[i] == k); }
    if(!ok){ cout << "No\n"; return; }
    if(n == 1) { cout << "Yes\n"; return; }
    for(int i = 2; i < n; i++)
        if(a[i - 1] >= k && a[i + 1] >= k) return cout << "Yes" << '\n', void(0);
    for(int i = 2; i <= n; i++)
        if(a[i - 1] >= k && a[i] >= k) return cout << "Yes" << '\n', void(0);
    cout << "No" << '\n';
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    int qwq; cin >> qwq; while(qwq--) solve();
    return 0;
}