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;
}
