Question

NOI OpenJudge 1.13.19 啤酒厂选址 代码查错与疑问

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
using namespace std;

const int N = 1007;
int a[N], d[N], s[N];

int main()
{
int n, i, j, p, tot = 0;
long long Res = 0x7fffffffffffffff, c;

cin >> n;
for (i = 1; i <= n; ++i) {scanf("%d%d", &a[i], &d[i]); tot += d[i]; s[i] = s[i - 1] + d[i];}

for (i = 1; i <= n; ++i)
{
c = 0;
for (j = 1; j <= n; ++j)
c += min(abs(s[j - 1] - s[i - 1]), abs(tot - s[j - 1] + s[i - 1])) * a[j];
if (c < Res) {Res = c; p = i;}
}

cout << p - 1 << ',' << Res << endl;

return 0;
}
//如上所示，为什么会WA 70分，为什么不能用前缀和的思想统计最短距离，最好能给出反例，谢谢
N复制上来的时候掉了一个0，原来提交的时候N=10007

Answer 1

你的N只有1007，而题目里有10000个点

追问

N复制上来的时候掉了一个0，原来提交的时候N=10007

追答

要注意前缀和的顺序。当i>j时，比如输入为
4
10 10
10 10
10 10
10 10
时
i=4,j=1时
原来一个方向花费是30，另一个方向是10

但因为tot - s[j - 1] + s[i - 1]中 s[j - 1] + s[i - 1]是正的，算出来变成了70。
所以正负要判断下