re?双指针

P1147 连续自然数和

@[zhangyuanjun](/user/1169121) 您犯了如下错误: #### 1. ```cpp while(l <= n && cnt[r] - cnt[l-1] <= n) r++; ``` 语句条件有误。因为您在此循环将指针 r 进行移动,也就是说可能导致数组越界的指针为 r 而非 l ,这个错误使 r 越界,导致RE。 **更正方式**:将 l<=n 改为 **r**<=n #### 2. 更改完以上代码,依然会导致0分(全WA)。这是因为: ```cpp if(cnt[r]-cnt[l-1]==n) printf("%d %d\n",l,r); ``` 这条程序。拿样例举例: 输入: ```cpp 10000 ``` 正确输出(如下)目前输出 ```cpp 18 142 18 142 297 328 297 328 388 412 388 412 1998 2002 1998 2002 10000 10000 ``` 因为一旦指针 l 与指针 r 重合,就会导致两个指针指向同一个数,这是不符题意的,毕竟:**每一段至少有两个数** **更正方式**:在输入前加入条件:指针 l **必须小于** r ------------ 其实我只是今天刚学 双指针 和 前缀和 的蒟蒻,如果更改后**无AC**,请 @ 我。 **达瓦里氏,您祝食用愉快** ------------ (注:根据这篇文章更改后的代码仅供参考,可能是卡着样例过的,若是有不严谨的用词,欢迎投诉QWQ)
by wushiyan @ 2024-02-04 15:51:05


我看了您的写法,由于运用了 双层循环,可能比较耗时,(~~应该是这样吧~~),我在这提供一种O(n)的做法,(~~应该是O(n)没错吧~~),也是双指针。 ```cpp //部分核心代码 int l=1,r=1; while(r<=m){ if(a[r]-a[l-1]==m){//这些连续的自然数段中的全部数之和如果等于m if(l<r){//并且 l 和 r 不重叠 cout<<l<<" "<<r<<endl;//输出正解 } r++;//下一个 }else if(a[r]-a[l-1]<m){//如果和小了 r++;//将 r 右移(扩大连续的自然数段的范围) }else{//如果和大了 l++;//将 l 右移(缩小连续的自然数段的范围) } } ``` ------------ **达瓦里氏,您祝食用愉快** ------------ (注:如果有反你谷社区规则,请及时告知我删除,若注释有误,也欢迎投诉)
by wushiyan @ 2024-02-04 16:16:21


@[wushiyan](/user/1152917) 谢谢大神指导,我过了ac
by zhangyuanjun @ 2024-02-07 13:13:28


@[wushiyan](/user/1152917) 神犇
by boluo777 @ 2024-04-05 22:06:47


|