【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
a1+a2+...+aka1a2+a3+...+ak+1<a3+a4+...+ak+2
->a2<ak+2
类似还可以推出
a3<ak+3
a4<ak+4
...
则有
a1<ak+1<a2k+1<a3k+1...
a2<ak+2<a2k+2<a3k+2...
...
也就是每隔k个要是递增的。
你的任务就是维护每隔k个数字递增。
我们先考虑a[1],a[1+k],a[1+2k],a[1+3k]...这个序列。
枚举所有不是问号的位置i,j(i < j) 且i+1..j-1之间的位置都是问号。
①
首先判断i-j-1是否大于等于a[j]-a[i]-1
因为如果不满足,显然这i-j-1个位置没办法按最小的递增顺序放满。肯定会不是严格递增的。
因此直接输出无解
②
接下来要考虑绝对值最小这个约束.来代替各个问号。
如果a[i]>=0 且a[j]>=0
那么按a[i]+1,a[i]+2..顺序递增代替问号就好
a[i]<=0且a[j]<=0,就a[j]-(i-j-1),a[j]-(i-j-1)+1....顺序递增
a[i]<0且a[j]>0的话,就从0的两边交替选数字就好,取出0两边交替的数字的最小值\(-\frac{(i-j-1)}{2}\),然后递增代替问号就可以。
当然要大于a[i]且小于等于a[j]-(i-j-1)
15e8-(-15e8)会爆long long.....
【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
const int INF = 105e7;
int n,k,a[N+10],b[N+10];
char s[20];
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> k;
for (int i = 1;i <= n;i++) {
cin >> s;
if (s[0]=='?'){
a[i] = INF;
}else {
a[i] = atoi(s);
}
}
for (int i = n+1;i <= n+k;i++) a[i] = INF+1;
for (int i = 1;i <= k;i++){
int tot = 0,prev = -INF;
for (int j = i;j <= n+k;j+=k)
if (a[j]==INF){
tot++;
}else{
if (a[j]- prev-1<tot){
return cout<<"Incorrect sequence"<<endl,0;
}
int s;
if (prev>=0)
s = prev+1;
else if (a[j]<=0) s = a[j]-tot;
else{
s = max(prev+1,min(-tot/2,a[j]-tot));
}
for (int kk = tot;kk >= 1;kk--){
a[j-k*kk] = s++;
}
prev = a[j];
tot=0;
}
}
for (int i = 1;i <= n;i++)
cout <<a[i]<<' ';
return 0;
}