求助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; }