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

全部评论
兄弟们,已经找大佬问到了,因为对于一个元素,有可能他符合前面的范围限制,但是为了跟后面满足,也会对其进行修改。例如1 1 5 7,k=2,按我的思路第二个1不改,然后改5和7,实际上将第二个符合条件的1修改为3后面就不用改了。本质上由于我的贪心只考虑前面的影响,但实际上每个元素还会影响到后面元素,所以不能这样贪心。
点赞 回复 分享
发布于 2023-11-13 10:24 天津

相关推荐

劝退式:感觉有人回才是不正常的
点赞 评论 收藏
分享
练习JAVA时长两年半:qps 30000
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务