数学（六） (2-2)

预处理出来从1到i的前缀以及后缀和（1＜=i＜=n），查询的时候查表即可得到。

void solve() {

int n;cin＞＞n;

vector＜int＞ a(n);

for (int i = 0; i＜n; i++) {

cin＞＞a[i];

}

vector＜int＞ l(n), r(n);//l[i]表示从0到i所需要花费的最小值

for (int i = 1; i＜n; i++) {

if (i == n - 1 || a[i + 1] - a[i]＞a[i] - a[i - 1]) {

l[i] = l[i - 1] + 1;

} else {

l[i] = l[i - 1] + a[i] - a[i - 1];

}

}

r[n - 1] = 0;

for (int i = n - 2; i ＞= 0; i--) {

if (i == 0 || a[i] - a[i - 1]＞a[i + 1] - a[i]) {

r[i] = r[i + 1] + 1;

} else {

r[i] = r[i + 1] + a[i + 1] - a[i];

}

}

int q;cin＞＞q;

while (q--) {

int x, y;

cin＞＞x＞＞y;

x--, y--;

int ans;

if (x＜y) {

ans = r[x] - r[y];

} else {

ans = l[x] - l[y];

}

cout＜＜ans＜＜"\n";

}

}

数学联邦政治世界观提示您：看后求收藏（同人小说网http://tongren.me），接着再看更方便。