刷一些 CF2000,进行一个录的记。
思路记录
- 首先观察到数列里的数不能凭空产生,所以初始序列必须含 \(k\)。
- 由于两个数的中位数是较小的那个,所以只要有一个与数列里的 \(k\) 相邻且比 \(k\) 大的数,就可以扩展到整个序列。
- 发现可以把第二条推广一下,不必要和 \(k\) 相邻,因为只要有两个相邻的比 \(k\) 大的数,就可以进行扩展到与 \(k\) 相邻。
- 问题就来到了如何产生一段长度大于 \(1\) 的比 \(k\) 大的数列。第三条是一种方法,还有一种就是两个大于 \(k\) 的数之间间隔一个任意数。(可以自己造几组样例手玩一下)
至此问题就得到了解决,一组数据时间复杂度 \(\mathcal{O(n)}\)。
代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
inline int read();
int T;
int n,k,a[N];
int main()
{
T=read();
while(T--)
{
bool flag=0;
n=read();k=read();
for(int i=1;i<=n;i++) a[i]=read();
if(n==1&&a[1]==k) {puts("yes");continue;}
for(int i=1;i<=n;i++) if(a[i]==k) flag=1;
if(!flag) {puts("no");continue;}
else flag=0;
for(int i=2;i<=n;i++)
{
if(a[i-1]>=k&&a[i]>=k) {puts("yes"),flag=1;break;}
}
if(!flag)
for(int i=2;i<n;i++)
{
if(a[i-1]>=k&&a[i+1]>=k) {puts("yes"),flag=1;break;}
}
if(!flag) puts("no");
}
return 0;
}
inline int read()
{
int x=0,f=1;
char ch;
ch=getchar();
while(ch>'9'||ch<'0'){if(ch=='-') f=-f;ch=getchar();}
while(ch<='9'&&ch>='0')
{
x=(x<<1)+(x<<3)+(ch&15);
ch=getchar();
}
return x*f;
}
标签:ch,puts,相邻,int,题解,CF1349B,read,flag,Orac
From: https://www.cnblogs.com/yzxgg/p/18316743