后面补了遍历啊a[i]=i;也就是数组下标和大小一一对应,还是错的。
by GREATchen @ 2023-11-04 21:10:08
@[GREATchen](/user/1176438) 首先您的代码时间复杂度 $O(M^2)$,不可能通过 $M \leq 2\times 10^6$ 的数据。
by Summer_Sheep @ 2023-11-04 21:10:31
前缀和时改为sum[i]=sum[i-1]+i;
by derekyang326 @ 2023-11-04 21:12:10
@[Summer_Sheep](/user/639085) 不是的,其实这个均摊复杂度应该是对的,因为你考虑到它有一个 break 的条件,所以说实际上在它 $\frac{(l+r)*(r-l+1)}{2}>m$时就break了,所以转化一下即可得到实际上 $r$ 枚举的范围其实是小于 $m/l$ 的所以这段代码的复杂度应该是比
```cpp
for(int i=1;i<=m/2;i++)
{
for(int j=1;j<=m/2/i;j++)
{
//....
}
}
```
下面这段低的,而下面这一段是一个调和级数的形式所以均摊复杂度是 $n\log n$
by h_rains @ 2023-11-04 21:17:16
@[h_rains](/user/665801) az,原来是这样的吗,膜拜。没怎么学过算复杂度/kk
by Summer_Sheep @ 2023-11-04 21:18:21
@[Summer_Sheep](/user/639085) 欸好像不对/yun,为什么它T了/yun,是不是楼主写的有问题()
by h_rains @ 2023-11-04 21:20:28
哦不对,我没算错是楼主写的有问题(
by h_rains @ 2023-11-04 21:22:36
```cpp
#include<iostream>
using namespace std;
const int N=1000010;
int sum[N],a[N],M;
int main(){
int exsum=0;
cin>>M;
for(int i=1;i<=M/2+1;i++){
sum[i]=sum[i-1]+i;
}
for(int l=1;l<=M/2;l++){
for(int r=l+1;r<=M/2+1;r++){
exsum=sum[r]-sum[l-1];
if(exsum==M){
printf("%d %d\n",l,r);
break;
}
if(exsum>M) break;
}
}
return 0;
}
```
by derekyang326 @ 2023-11-04 21:30:04
@[GREATchen](/user/1176438) 看一下我改的代码(改成了我的码风,请谅解)
by derekyang326 @ 2023-11-04 21:35:23
@[GREATchen](/user/1176438)
首先你的前缀和写错了,a数组没有任何意义。应该是`sum[i]=sum[i-1]+i;`。
其次`sum[i]`是1到i的和,所以l到r的和应该是`sum[r]-sum[l-1]`。
by PeaceSunset @ 2023-11-04 21:52:59