我的数组是从0开始索引,所以中位数n/2哪里应该没有问题。。。
by Ranger_R @ 2022-11-30 19:42:56
print那个函数只是写的玩的哈。。。也没有用到
by Ranger_R @ 2022-11-30 19:46:50
呃,您不是已经切了这道题吗
by Coffins @ 2022-11-30 20:23:36
@[Coffins](/user/615965) 用的是题解的答案过的。。。我的才60分。。。看着是一样的意思,但是我的就是过不了数据点4、5、9、10
by Ranger_R @ 2022-12-02 10:52:52
解决了。。。主要改了两点
1.
```cpp
c[i] = c[i-1] + a[i-1] - ave;
```
按照我的理解,这里的x[i]指的不是题解里的第a[i]个小朋友给左边的人的数量,因为如果给的是右边,正负关系相反之后表达式ave=a[i]-x[i]+x[i+1]就不成立了(x[i]是负数,向右给,实际上应该是减少了,但是减去负数反而增加了)
我的理解是x[i]是指的第a[i-1]个和第a[i]个小朋友之间传递的次数,这样正就是a[i]减少,负就是a[i]增加
而这样理解的话,那么这里的c[i]就应该是减去ave,加上a[i-1],而不是题解里的那个加上ave减去a[i-1],题解里的应该是另外一种理解但我不知道。。。
2.所有的int都改成了long long int,解决了有的数据点直接就没有答案的问题,就通过了
最终代码:
```cpp
# include <iostream>
# include <algorithm>
# include <numeric>
using namespace std;
int main()
{
cin.tie(nullptr)->sync_with_stdio(false);
long long int n, ave;
long long int a[1000005];
cin >> n;
for (int i=0; i<n; i++)
{
cin >> a[i];
ave += a[i];
}
ave /= n;
long long int c[1000005];
long long int ans = 0;
c[0] = 0;
for (int i=1; i<n; i++)
{
c[i] = c[i-1] + a[i-1] - ave;
}
sort(c, c+n);
long long int mid = c[n/2];
for (int i=0; i<n; i++)
{
ans += abs(mid-c[i]);
}
cout << ans;
return 0;
}
```
by Ranger_R @ 2022-12-02 11:16:28