Description
给定N个数,第 i 个数的形态描述为一个正整数 Ai,定义形态i 和形态j 的差异为|Ai - Aj|。
SSY在给定一个指令后会发生形态变化,它会从当前形态变化为其他形态中与其差异第 K 小的形态。如果差异第 K小的形态不是唯一的,那么它会变化为 Ai 比较小的那个形态。
SSY 的好奇心驱使,他想知道从每个形态开始接受一个指令后会是什么形态。
Input
第一行包含两个整数 N, K。
之后一行包含 N个整数 A1, A2, A3, ..., AN-1, AN。
Output
一行内输出 N个整数 S1, S2, S3, ..., SN-1, SN,其中 Si 表示从形态 i变化一次之后的形态描述值。行末有一空格
Sample Input
5 2
1 2 4 7 10
Sample Output
4 4 1 4 4
HINT
对于 100% 的数据,1≤K<N≤10^6,1≤A1<A2<...<AN≤10^18 。
Solve
维护一个区间[L,R),让L或者R-1始终是答案。
居然没想到。。。%jms大佬
Code
#include <bits/stdc++.h>
using namespace std;
long long nextLong()
{
long long ret=0;
char a;
a=getchar();
while(!isdigit(a))
{
a=getchar();
}
while(isdigit(a))
{
ret=ret*10+a-'0';
a=getchar();
}
return ret;
}
long long A[10+int(1e6)];
int main()
{
long long N,K;
N=nextLong();
K=nextLong();
for(long long i=0;i<N;++i)
{
A[i]=nextLong();
}
int L=0,R=K+1;
for(long long i=0;i<N;++i)
{
while(i>R-1)
{
L++;
R++;
}
while(R<N&&A[R]-A[i]<A[i]-A[L])
{
L++;
R++;
}
if(A[R-1]-A[i]>A[i]-A[L])
{
cout<<A[R-1]<<' ';
}
else
{
cout<<A[L]<<' ';
}
}
}