求助G题枚举开头元素加维护上下界思路为什么wa了
G题我的思路是,枚举第一个元素的值从1到7,然后往后遍历数组。维护一个上下界,l,r,表示下一个元素应该在的范围。
比如枚举开头元素为st,则,下一个元素应该在st-k到st+k之间(两边对1和7取一下max和min边界处理一下),如果下一个元素是在这个范围内,则更新l和r为这个元素+-k的位置。
关键在于如果这个元素ai不在l和r范围内,则计数器加一,更新l和r为原来的l和r再往外扩张k范围,表示将这个元素挪到跟前一个元素符合k距离的情况下,最多能满足下一个元素符合k距离的上下界。
就这样一直维护下去,跑7遍取最小值,最后只能过80%的数据,求问这个思路哪里错了,或者求hack数据。
代码如下:
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1e5+10;
int arr[maxn];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int ans=inf;
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>arr[i];
for(int st=1;st<=7;st++){
int temans=0;
if(st!=arr[1]) temans++;
int prel=max(st-k,1),prer=min(st+k,7);
for(int i=2;i<=n;i++){
if(arr[i]<prel||arr[i]>prer){
temans++;
prel=max(1,prel-k);
prer=min(7,prer+k);
}
else{
prel=max(arr[i]-k,1);
prer=min(arr[i]+k,7);
}
}
ans=min(ans,temans);
}
cout<<ans<<endl;
return 0;
}
