近幾天看了一下2019省賽的題目权均，其他題基本沒什么營養(yǎng)垛叨。
最后一題還是有難度的全肮，有CF思維題內(nèi)味兒了.特此記錄一下.
題面:
思路:
發(fā)現(xiàn)一次操作,整體的和是不變的.觀察其前綴和.
?a1 a2 a3 -> s1 s2 s3.??
觀察對a2操作.?
?s1 變?yōu)?s1 + a2 = s2
s2 變?yōu)?s2 - 2*a2 +a2 = s1.
s3 不變.
轉(zhuǎn)換成前綴和S后就相當(dāng)于讓你合理安排順序使得兩個相鄰的數(shù)的差值的最大值最小.顯然將其排序可做到這一點.
又發(fā)現(xiàn):對某個點i操作以后相當(dāng)于si-1 和 si 互換.所以直接排序可行册舞。
最后注意一點,由題意可知Sn是不能參與排序的播演，所以要特判Sn.
方法:枚舉所有i ∈(1,n-1),swap(s[i],s[n-1]),然后跟Sn作差.(swap就可以趾代，其他地方盡量保持有序)
代碼:
```
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
#define ll long long
ll sum[maxn];
int main()
{
? ? int t;
? ? scanf("%d",&t);
? ? while(t--)
? ? {
? ? ? ? int n;
? ? ? ? scanf("%d",&n);
? ? ? ? for(int i = 1;i<=n;i++)
? ? ? ? {
? ? ? ? ? ? scanf("%lld",&sum[i]);
? ? ? ? ? ? sum[i]+=sum[i-1]; //求前綴和
? ? ? ? }
? ? ? ? sort(sum + 1,sum + n);
? ? ? ? ll ans = -1;
? ? ? ? for(int i = 1;i<=n;i++)
? ? ? ? ? ? ans = max(ans,abs(sum[i] - sum[i-1]));
? ? ? ? //最后一個不能排序贯底，那么枚舉,但是同時要保證其他地方的差值盡量變化不大
? ? ? ? ll res = -1;
? ? ? ? for(int i = 1;i<=n - 2;i++)
? ? ? ? {
? ? ? ? ? ? swap(sum[i],sum[n-1]);
? ? ? ? ? ? res = max(abs(sum[i] - sum[i-1]),abs(sum[i+1] - sum[i]));
? ? ? ? ? ? res = max(res,abs(sum[n] - sum[n-1]));
? ? ? ? ? ? res = max(res,abs(sum[n-1] - sum[n-2]));
? ? ? ? ? ? ans = min(res,ans);
? ? ? ? ? ? swap(sum[n-1],sum[i]);
? ? ? ? }
? ? ? ? printf("%lld\n",ans);
? ? }
? ? return 0;
}
/*
3
3
5 -2 3
*/
/*
#include <algorithm>
#include <cstring>
#include <iostream>
#include <limits.h>
using namespace std;
typedef long long LL;
const int N = 300010;
int n;
LL sum[N], a[N], s0, sn;
bool st[N];
int main()
{
? ? int T;
? ? scanf("%d", &T);
? ? while (T--)
? ? {
? ? ? ? scanf("%d", &n);
? ? ? ? sum[0] = 0;
? ? ? ? for (int i = 1; i <= n; i++)
? ? ? ? {
? ? ? ? ? ? scanf("%lld", &sum[i]);
? ? ? ? ? ? sum[i] += sum[i - 1];
? ? ? ? }
? ? ? ? s0 = sum[0], sn = sum[n];
? ? ? ? if (s0 > sn)
? ? ? ? ? ? swap(s0, sn);
? ? ? ? sort(sum, sum + n + 1);
? ? ? ? for (int i = 0; i <= n; i++)
? ? ? ? ? ? if (s0 == sum[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? s0 = i;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? for (int i = n; i >= 0; i--)
? ? ? ? ? ? if (sn == sum[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? sn = i;
? ? ? ? ? ? ? ? break;
? ? ? ? ? ? }
? ? ? ? memset(st, 0, sizeof st);
? ? ? ? int l = 0, r = n;
? ? ? ? for (int i = s0; i >= 0; i -= 2)
? ? ? ? {
? ? ? ? ? ? a[l++] = sum[i];
? ? ? ? ? ? st[i] = true;
? ? ? ? }
? ? ? ? for (int i = sn; i <= n; i += 2)
? ? ? ? {
? ? ? ? ? ? a[r--] = sum[i];
? ? ? ? ? ? st[i] = true;
? ? ? ? }
? ? ? ? for (int i = 0; i <= n; i++)
? ? ? ? ? ? if (!st[i])
? ? ? ? ? ? {
? ? ? ? ? ? ? ? a[l++] = sum[i];
? ? ? ? ? ? }
? ? ? ? LL res = 0;
? ? ? ? for (int i = 1; i <= n; i++)
? ? ? ? ? ? res = max(res, abs(a[i] - a[i - 1]));
? ? ? ? printf("%d\n", res);
? ? }
? ? return 0;
}
*/
/*
3
5
1 2 3 4 5
4
-1 -5 10 20
7
1 1 3 6 -8 -8 5
5
20
8
*/
```
