D. Orac and Medians(贪心 + 构造)
Problem - D - Codeforces
史莱姆有—系列正整数个2个…., .n个
在一个操作中，Orac可以选择任意子段( ...r]并替换所有值一;个布..，到中位数的值{T;T分.，一打
在这个问题中，对于整数多集s，中位数s等于[产]-其中最小的数字。例如，中位数{1，4，4，鹦4和[1，7，5是B}
史莱姆希望奥拉克制作一i午2午..=n个k使用这些操作。
奥拉克认为这是不可能的，他不想浪费时间，所以他决定问问你是否有可能满足史莱姆的要求，他可能会问你这些问题好几次。输入
输入的第一行是单个整数t:查询数。
每个查询的第一行包含两个整数n (1<n≤100 000和k (1<k<10)第二行包含n正整数一一;z1
..., n(1≤我企109)
的总和n最多是100000 .
输出
输出应包含t线。这我n行应等于"yes”，如果可以生成所有整数k在某些操作中或"否"，否则。您可以以小写或大写形式打印每个字母。
Example
input
Copy
5 5 3 1 5 2 6 1 1 6 6 3 2 1 2 3 4 3 3 1 2 3 10 3 1 2 3 4 5 6 7 8 9 10
output
Copy
no yes yes no yes
请注意在第一个查询中，Orac不能将所有元素都转换为3。在第二个查询中，a1= 6已经被满足。在第三个查询中，Orac可以选择完整的数组并将所有元素转换为2。在第四个查询中，Orac不能将所有元素都转换为3。在第5个查询中，Orac可以先选择[1,6]，然后选择[2,10]。
题解:
首先很容易看出来,如果数组中无k,肯定不行,如果数组中有两个或,两个以上连续的k,一定可以,可以一次改变一个相邻的为k,直到所有变成k,
那么思考的方向就变成了,可以构成长度至少大于2的连续的k,如果区间p是偶数,第p/2大的应该是k,如果区间是奇数,第(p+1)/2大的应该是k,
我们为了方便考虑,可以先把大于等于ai的变为1,其余变为0,由于我们已经判断是数组中是否有k,
如果k相邻的是一个>=k的,可以都变为k,符合题意
如果是两个都大于k的相邻呢?其实也是可以的,两个都大于k的也可以继续扩展,直到遇到 等于k的,
把与k相邻的那个与k进行操作,都等于k,符合题意
如果是奇数,三个位置,(根据中位数的性质)有两个位置大于等于k就行,
最后特解,n = 1,并且k存在
#include <cstdio>
#include <cstring>
#include <algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
#define int long long
int a[200005];
void solve()
{int n,k;cin >> n >> k;int f = 0;for(int i = 1;i <= n;i++){cin >> a[i];if(a[i] == k)f = 1;a[i] = (a[i] >= k);}if(!f){cout <<"no\\n";return ;}for(int i = 1;i <= n -1;i++){if(i + 2 <= n){if(a[i] + a[i + 1] + a[i + 2] >= 2){f = 0;}}if(a[i] + a[i + 1] >= 2){f = 0;}}if(!f || n == 1){cout << "yes\\n";}else{cout <<"no\\n";}
}signed main()
{
// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);int t = 1;cin >> t;while(t--){solve(); }
}
