(1) 如果a[i] < 0 则从两边提取灵能
(2) 如果a[i] > 0 则从两边分配灵能
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 3e5 + 10;
int n; //n名高阶圣堂武士
long long a[N], s[N]; //a[N]用来存每名武士的灵能值,s[N]前缀和
bool st[N];
int main()
{
int T;
scanf("%d", &T); //T组测试数据
while (T -- )
{
scanf("%d", &n); //输入有多少名武士
s[0] = 0;
for (int i = 1; i <= n; i ++ )
{
scanf("%lld", &a[i]);
s[i] = s[i - 1] + a[i];
}
long long s0 = s[0], sn = s[n]; //因为首尾两个武士是没有办法传输灵能的,所以先标记下来
if (s0 > sn) swap(s0, sn); //因为两种情况是对称的,这里只要考虑s0小的这种情况即可
sort(s, s + n + 1);
for (int i = 0; i <= n; i ++ ) //找到起点的位置
if (s[i] == s0)
{
s0 = i;
break;
}
for (int i = n; i >= 0; i -- ) //找到终点的位置
if (s[i] == sn)
{
sn = i;
break;
}
memset(st, 0, sizeof st);
int l = 0, r = n;
for (int i = s0; i >= 0; i -= 2)
{
a[l ++ ] = s[i];
st[i] = true;
}
for (int i = sn; i <= n; i += 2)
{
a[r -- ] = s[i];
st[i] = true;
}
for (int i = 0; i <= n; i ++ )
if (!st[i]) a[l ++ ] = s[i];
long long res = 0;
for (int i = 1; i <= n; i ++ ) res = max(res, abs(a[i] - a[i - 1]));
printf("%lld\n", res);
}
return 0;
}
请问一下,第一个for循环后面,排在第一个的武士不应该是s[1]吗?为什么是s[0]?