【题目描述】
给定一个长度为
N
N
N的数组，数组中的第
i
i
i个数字表示一个给定股票在第
i
i
i天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
【输入格式】
第一行包含整数
N
N
N，表示数组长度。
第二行包含
N
N
N个不大于
10000
10000
10000的正整数，表示完整的数组。
【输出格式】
输出一个整数，表示最大利润。
【数据范围】
1
≤
N
≤
1
0
5
1≤N≤10^5
1≤N≤105
【输入样例1】
6 7 1 5 3 6 4
【输出样例1】
7
【输入样例2】
5 1 2 3 4 5
【输出样例2】
4
【输入样例3】
5 7 6 4 3 1
【输出样例3】
0
【分析】
任何时间跨度大于一天的交易都可以拆分成多个时间跨度为一天的交易，那么只要后一天的价格比前一天高，那么我们就在前一天买，后一天卖，因此利润就加上 a [ i + 1 ] − a [ i ] a[i+1]-a[i] a[i+1]−a[i]，枚举所有跨度为一天的交易，如果利润大于 0 0 0就进行交易，最后的利润即为最大值。
【代码】
#include二、AcWing 104. 货仓选址#include #include using namespace std; const int N = 100010; int a[N]; int n, res; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n - 1; i++) if (a[i + 1] - a[i] > 0) res += a[i + 1] - a[i]; cout << res << endl; return 0; }
【题目描述】
在一条数轴上有
N
N
N家商店，它们的坐标分别为
A
1
∼
A
N
A_1sim A_N
A1∼AN。
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
【输入格式】
第一行输入整数
N
N
N。
第二行
N
N
N个整数
A
1
∼
A
N
A_1∼A_N
A1∼AN。
【输出格式】
输出一个整数，表示距离之和的最小值。
【数据范围】
1
≤
N
≤
100000
1≤N≤100000
1≤N≤100000
0
≤
A
i
≤
40000
0≤A_i≤40000
0≤Ai≤40000
【输入样例】
4 6 2 9 1
【输出样例】
12
【分析】
货仓的坐标为各商店坐标的中位数~
【代码】
#include三、AcWing 122. 糖果传递#include #include using namespace std; const int N = 100010; int a[N]; int n, res; int main() { cin >> n; for (int i = 0; i < n; i++) cin >> a[i]; nth_element(a, a + n / 2, a + n); for (int i = 0; i < n; i++) res += abs(a[i] - a[n / 2]); cout << res << endl; return 0; }
【题目描述】
有
n
n
n个小朋友坐成一圈，每人有
a
[
i
]
a[i]
a[i]个糖果。
每人只能给左右两人传递糖果。
每人每次传递一个糖果代价为
1
1
1。
求使所有人获得均等糖果的最小代价。
【输入格式】
第一行输入一个正整数
n
n
n，表示小朋友的个数。
接下来
n
n
n行，每行一个整数
a
[
i
]
a[i]
a[i]，表示第
i
i
i个小朋友初始得到的糖果的颗数。
【输出格式】
输出一个整数，表示最小代价。
【数据范围】
1
≤
n
≤
1000000
1≤n≤1000000
1≤n≤1000000
0
≤
a
[
i
]
≤
2
×
1
0
9
0≤a[i]≤2×10^9
0≤a[i]≤2×109
数据保证一定有解
【输入样例】
4 1 2 5 4
【输出样例】
4
【分析】
设
1
1
1号给
2
2
2号
x
1
x_1
x1个糖果，
2
2
2号给
3
3
3号
x
2
x_2
x2个，以此类推，设最后每人的糖果都为
b
b
b个，
b
=
(
a
1
+
⋯
+
a
n
)
/
n
b=(a_1+dots +a_n)/n
b=(a1+⋯+an)/n
则本题要求的为最小化
∣
x
1
∣
+
∣
x
2
∣
+
⋯
+
∣
x
n
∣
|x_1|+|x_2|+dots +|x_n|
∣x1∣+∣x2∣+⋯+∣xn∣
则
1
1
1号的糖果为
a
1
−
x
1
+
x
n
=
b
a_1-x_1+x_n=b
a1−x1+xn=b，
2
2
2号的糖果为
a
2
−
x
2
+
x
1
=
b
…
a_2-x_2+x_1=bdots
a2−x2+x1=b…
转换后方程为
x
1
=
x
n
−
(
b
−
a
1
)
x_1=x_n-(b-a_1)
x1=xn−(b−a1)，
x
2
=
x
n
−
(
2
b
−
a
1
−
a
2
)
,
…
,
x
n
−
1
=
x
n
−
(
(
n
−
1
)
b
−
a
1
−
a
2
−
⋯
−
a
n
−
1
)
x_2=x_n-(2b-a_1-a_2),dots ,x_{n-1}=x_n-((n-1)b-a_1-a_2-dots -a_{n-1})
x2=xn−(2b−a1−a2),…,xn−1=xn−((n−1)b−a1−a2−⋯−an−1)，
x
n
=
x
n
−
(
n
b
−
a
1
−
⋯
−
a
n
)
x_n=x_n-(nb-a_1-dots -a_n)
xn=xn−(nb−a1−⋯−an)即为
x
n
=
x
n
x_n=x_n
xn=xn，则该式可移除。
将方程组带入上式得
∣
x
n
−
(
b
−
a
1
)
∣
+
∣
x
n
−
(
2
b
−
a
1
−
a
2
)
∣
+
⋯
+
∣
x
n
−
0
∣
|x_n-(b-a_1)|+|x_n-(2b-a_1-a_2)|+dots +|x_n-0|
∣xn−(b−a1)∣+∣xn−(2b−a1−a2)∣+⋯+∣xn−0∣
记为
∣
x
−
c
0
∣
+
∣
x
−
c
1
∣
+
⋯
+
∣
x
−
c
n
−
1
∣
|x-c_0|+|x-c_1|+dots +|x-c_{n-1}|
∣x−c0∣+∣x−c1∣+⋯+∣x−cn−1∣，要使该式最小，则
x
x
x应取
c
c
c的中位数。
【代码】
#include四、AcWing 112. 雷达设备#include #include using namespace std; typedef long long LL; const int N = 1000010; LL s[N], c[N]; int n; int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) { scanf("%d", &s[i]); s[i] += s[i - 1]; } LL b = s[n] / n;//平均值 int k = 0; for (int i = 1; i <= n; i++) c[k++] = i * b - s[i]; nth_element(c, c + k / 2, c + k); LL res = 0; for (int i = 0; i < k; i++) res += abs(c[i] - c[k / 2]); printf("%lldn", res); return 0; }
【题目描述】
假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。
每个小岛都位于海洋一侧的某个点上。
雷达装置均位于海岸线上，且雷达的监测范围为
d
d
d，当小岛与某雷达的距离不超过
d
d
d时，该小岛可以被雷达覆盖。
我们使用笛卡尔坐标系，定义海岸线为
x
x
x轴，海的一侧在
x
x
x轴上方，陆地一侧在
x
x
x轴下方。
现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。
【输入格式】
第一行输入两个整数
n
n
n和
d
d
d，分别代表小岛数目和雷达检测范围。
接下来
n
n
n行，每行输入两个整数，分别代表小岛的
x
,
y
x,y
x,y轴坐标。
同一行数据之间用空格隔开。
【输出格式】
输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出
−
1
-1
−1。
【数据范围】
1
≤
n
≤
1000
1≤n≤1000
1≤n≤1000
−
1000
≤
x
,
y
≤
1000
-1000≤x,y≤1000
−1000≤x,y≤1000
【输入样例】
3 2 1 2 -3 1 2 1
【输出样例】
2
【分析】
每个小岛在海岸线上都有一个区间 [ l , r ] [l,r] [l,r]，当把雷达放在这个区间内时小岛就能被覆盖，易知区间的两个端点为： l = x − ( d 2 − y 2 ) , r = x + ( d 2 − y 2 ) l=x-(d^2-y^2),r=x+(d^2-y^2) l=x−(d2−y2),r=x+(d2−y2)，示意图如下：
那么问题就转化成：给定若干区间，最少选择多少个点，使得每个区间上至少包含一个选中的点。
【代码】
#include五、AcWing 1235. 付账问题#include #include #include using namespace std; const int N = 1010; int n, d; bool st; struct Edge { double l, r; bool operator< (const Edge& t) const { return r < t.r; } }e[N]; int main() { cin >> n >> d; for (int i = 0; i < n; i++) { int x, y; cin >> x >> y; if (y > d) st = true; else { double t = sqrt(d * d - y * y); e[i].l = x - t, e[i].r = x + t; } } if (st) { cout << -1 << endl; return 0; } sort(e, e + n); int cnt = 0; double ed = -1e18; for (int i = 0; i < n; i++) if (ed < e[i].l) { cnt++, ed = e[i].r; } cout << cnt << endl; return 0; }
【题目描述】
几个人一起出去吃饭是常有的事。
但在结帐的时候，常常会出现一些争执。
现在有
n
n
n个人出去吃饭，他们总共消费了
S
S
S元。
其中第
i
i
i个人带了
a
i
a_i
ai元。
幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
为了公平起见，我们希望在总付钱量恰好为
S
S
S的前提下，最后每个人付的钱的标准差最小。
这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是
1
1
1分钱的整数倍。
你需要输出最小的标准差是多少。
标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。
形式化地说，设第
i
i
i个人付的钱为
b
i
b_i
bi元，那么标准差为：
s
=
(
b
1
−
S
/
n
)
2
+
(
b
2
−
S
/
n
)
2
+
⋯
+
(
b
n
−
S
/
n
)
2
n
s=sqrt{frac{(b_1-S/n)^2+(b_2-S/n)^2+dots +(b_n-S/n)^2}{n}}
s=n(b1−S/n)2+(b2−S/n)2+⋯+(bn−S/n)2
。
【输入格式】
第一行包含两个整数
n
,
S
n,S
n,S；
第二行包含
n
n
n个非负整数
a
1
,
…
,
a
n
a_1,dots ,a_n
a1,…,an。
【输出格式】
输出最小的标准差，四舍五入保留
4
4
4位小数。
【数据范围】
1
≤
n
≤
5
×
1
0
5
1≤n≤5×10^5
1≤n≤5×105
0
≤
a
i
≤
1
0
9
0≤a_i≤10^9
0≤ai≤109
0
≤
S
≤
1
0
15
0≤S≤10^{15}
0≤S≤1015
【输入样例1】
5 2333 666 666 666 666 666
【输出样例1】
0.0000
【输入样例2】
10 30 2 1 4 7 4 8 3 6 4 7
【输出样例2】
0.7928
【分析】
设 x 1 + x 2 + ⋯ + x n = c x_1+x_2+dots +x_n=c x1+x2+⋯+xn=c为一个定值，则： x 1 2 + x 2 2 + ⋯ + x n 2 n ≥ ( x 1 + x 2 + ⋯ + x n n ) 2 frac{x_1^2+x_2^2+dots +x_n^2}{n}ge (frac{x_1+x_2+dots +x_n}{n})^2 nx12+x22+⋯+xn2≥(nx1+x2+⋯+xn)2，且 x 1 = x 2 = ⋯ = x n = c / n x_1=x_2=dots =x_n=c/n x1=x2=⋯=xn=c/n时取到最小值。
令 b i − S / n = x i b_i-S/n=x_i bi−S/n=xi，则 x 1 + x 2 + ⋯ + x n = 0 x_1+x_2+dots +x_n=0 x1+x2+⋯+xn=0，因此 ( b 1 − S / n ) 2 + ( b 2 − S / n ) 2 + ⋯ + ( b n − S / n ) 2 n ≥ 0 sqrt{frac{(b_1-S/n)^2+(b_2-S/n)^2+dots +(b_n-S/n)^2}{n}}ge 0 n(b1−S/n)2+(b2−S/n)2+⋯+(bn−S/n)2 ≥0。要使式子最小化，应使 b i b_i bi最接近 S / n S/n S/n。
对于第 i i i个同学，有两种情况：
a
i
≥
S
/
n
a_ige S/n
ai≥S/n：那么该同学出的钱即为平均数，即
b
i
=
S
/
n
b_i=S/n
bi=S/n；
a
i
<
S
/
n
a_i我们记
a
v
g
=
S
/
n
avg=S/n
avg=S/n，然后按钱数从小到大枚举每个同学，假设当前总共还需要出
S
′
S'
S′元，还剩下
n
′
n'
n′个同学需要出钱，那么当前同学
i
i
i理论需要出的钱为
c
u
r
=
S
′
/
n
′
cur=S'/n'
cur=S′/n′，如果该同学的钱
a
i
a_i
ai不足
c
u
r
cur
cur，那么就出
a
i
a_i
ai元，然后计算一下
t
+
=
(
a
i
−
a
v
g
)
2
t+=(a_i-avg)^2
t+=(ai−avg)2，最后要更新一下
S
′
−
=
a
i
,
n
′
−
−
S'-=a_i,n'--
S′−=ai,n′−−。
t
/
n
sqrt{t/n}
t/n
即为答案。
注意本题使用double的精度不够，需要使用long double。
【代码】
#include六、AcWing 1239. 乘积最大#include #include #include using namespace std; typedef long long LL; const int N = 500010; int n, a[N]; long double s; int main() { scanf("%d%llf", &n, &s); for (int i = 0; i < n; i++) scanf("%d", &a[i]); sort(a, a + n); long double t = 0, avg = s / n; for (int i = 0; i < n; i++) { double cur = s / (n - i);//当前每个同学需要均摊的钱数 if (a[i] < cur) cur = a[i]; t += (cur - avg) * (cur - avg); s -= cur; } printf("%.4llfn", sqrt(t / n)); return 0; }
【题目描述】
给定
N
N
N个整数
A
1
,
A
2
,
…
,
A
N
A_1,A_2,dots ,A_N
A1,A2,…,AN。
请你从中选出
K
K
K个数，使其乘积最大。
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以
1
0
9
+
9
10^9+9
109+9的余数。
注意，如果
X
<
0
X<0
X<0，我们定义
X
X
X除以
1
0
9
+
9
10^9+9
109+9的余数是
(
−
X
)
(-X)
(−X)除以
1
0
9
+
9
10^9+9
109+9的余数，即：
0
−
(
(
0
−
x
)
%
(
1
0
9
+
9
)
)
0-((0-x)%(10^9+9))
0−((0−x)%(109+9))。
【输入格式】
第一行包含两个整数
N
N
N和
K
K
K。
以下
N
N
N行每行一个整数
A
i
A_i
Ai。
【输出格式】
输出一个整数，表示答案。
【数据范围】
1
≤
K
≤
N
≤
1
0
5
1≤K≤N≤10^5
1≤K≤N≤105
−
1
0
5
≤
A
i
≤
1
0
5
-10^5≤A_i≤10^5
−105≤Ai≤105
【输入样例1】
5 3 -100000 -10000 2 100000 10000
【输出样例1】
999100009
【输入样例2】
5 3 -100000 -100000 -2 -100000 -100000
【输出样例2】
-999999829
【分析】
首先我们先将整个序列从小到大排好序，然后分情况讨论：
k
=
n
k=n
k=n：则答案就是整个序列的乘积；
k
≠
n
kne n
k=n：需要分别讨论
k
k
k为奇数与
k
k
k为偶数的情况：
（1）
k
k
k为偶数：则最终结果一定非负，我们成对枚举负数或正数，假设当前
l
l
l指向序列的最左边，
r
r
r指向最右边，那么我们需要选
a
[
l
]
∗
a
[
l
+
1
]
a[l]*a[l+1]
a[l]∗a[l+1]与
a
[
r
]
∗
a
[
r
−
1
]
a[r]*a[r-1]
a[r]∗a[r−1]中最大的，然后将相应的指针向后移两位，不断重复此操作直到选出
k
k
k个数为止；
（2）
k
k
k为奇数：首先我们先把最大的数选了，即
a
[
r
]
a[r]
a[r]，然后判断
a
[
r
]
a[r]
a[r]是否为负数，如果为负数，说明整个序列都是负数，那么最后的结果一定为负，因此我们成对选择的时候需要选择乘积更小的；否则最后的结果一定还是非负，那么选法同（1）。
【代码】
#include七、AcWing 1247. 后缀表达式#include #include using namespace std; typedef long long LL; const int N = 100010, MOD = 1e9 + 9; LL a[N]; int n, k; int main() { cin >> n >> k; for (int i = 0; i < n; i++) cin >> a[i]; sort(a, a + n); LL res = 1; int l = 0, r = n - 1, sign = 1;//如果序列全为负数则sign为-1 if (k % 2)//k为奇数就先把最大的数选了 { res = a[r--]; k--; if (res < 0) sign = -1; } while (k)//k为偶数的情况 { LL x = a[l] * a[l + 1], y = a[r] * a[r - 1]; if (x * sign > y * sign) { res = x % MOD * res % MOD;//注意要先取余数 l += 2; } else { res = y % MOD * res % MOD; r -= 2; } k -= 2; } cout << res << endl; return 0; }
【题目描述】
给定
N
N
N个加号、
M
M
M个减号以及
N
+
M
+
1
N+M+1
N+M+1个整数
A
1
,
A
2
,
…
,
A
N
+
M
+
1
A_1,A_2,dots ,A_{N+M+1}
A1,A2,…,AN+M+1，小明想知道在所有由这
N
N
N个加号、
M
M
M个减号以及
N
+
M
+
1
N+M+1
N+M+1个整数凑出的合法的后缀表达式中，结果最大的是哪一个？
请你输出这个最大的结果。
例如使用
123
+
−
123+-
123+−，则23+1-这个后缀表达式结果是
4
4
4，是最大的。
【输入格式】
第一行包含两个整数
N
N
N和
M
M
M。
第二行包含
N
+
M
+
1
N+M+1
N+M+1个整数
A
1
,
A
2
,
…
,
A
N
+
M
+
1
A_1,A_2,dots ,A_{N+M+1}
A1,A2,…,AN+M+1。
【输出格式】
输出一个整数，代表答案。
【数据范围】
0
≤
N
,
M
≤
1
0
5
0≤N,M≤10^5
0≤N,M≤105
−
1
0
9
≤
A
i
≤
1
0
9
-10^9≤A_i≤10^9
−109≤Ai≤109
【输入样例】
1 1 1 2 3
【输出样例】
4
【分析】
后缀表达式是可以改变运算的顺序的，也就是可以给式子加括号，假设我们有 N N N个加号， M M M个减号，那么可以有如下式子：
b − a 1 − a 2 − a 3 − a 4 + a 5 + a 6 b-a_1-a_2-a_3-a_4+a_5+a_6 b−a1−a2−a3−a4+a5+a6 b − ( a 1 − a 2 − a 3 − a 4 ) + a 5 + a 6 b-(a_1-a_2-a_3-a_4)+a_5+a_6 b−(a1−a2−a3−a4)+a5+a6 b − a 1 − a 2 − a 3 − ( a 4 + a 5 + a 6 ) b-a_1-a_2-a_3-(a_4+a_5+a_6) b−a1−a2−a3−(a4+a5+a6)
因此我们可以凑出 1 ∼ N + M 1sim N+M 1∼N+M中的任意数量的负号，同理加号也是如此，那么我们分以下两种情况讨论：
-
M
=
0
M=0
M=0，即全都为加号，那么答案就是所有数之和；
M
≠
0
Mne 0
M=0，那么我们由于至少需要加一个数减一个数，那么就用序列中的最大值
m
a
x
v
maxv
maxv减去最小值
m
i
n
v
minv
minv，然后剩余的数中既可以加也可以减，那么就加上正数减去负数，即加上剩余所有数的绝对值就为答案。
【代码】
#include八、AcWing 1248. 灵能传输#include #include #include using namespace std; typedef long long LL; const int N = 200010; LL a[N]; int n, m; int main() { cin >> n >> m; int cnt = n + m + 1; for (int i = 0; i < cnt; i++) cin >> a[i]; sort(a, a + cnt); LL res = 0; if (!m)//特判负号为0的情况 for (int i = 0; i < cnt; i++) res += a[i]; else { res = a[cnt - 1] - a[0];//加上一个最大的数再减去一个最小的数 for (int i = 1; i < cnt - 1; i++) res += abs(a[i]); } cout << res << endl; return 0; }
【题目描述】
在游戏《星际争霸II》中，高阶圣堂武士作为星灵的重要AOE单位，在游戏的中后期发挥着重要的作用，其技能”灵能风暴“可以消耗大量的灵能对一片区域内的敌军造成毁灭性的伤害。
经常用于对抗人类的生化部队和虫族的刺蛇飞龙等低血量单位。
你控制着
n
n
n名高阶圣堂武士，方便起见标为
1
,
2
,
…
,
n
1,2,dots ,n
1,2,…,n。
每名高阶圣堂武士需要一定的灵能来战斗，每个人有一个灵能值
a
i
a_i
ai表示其拥有的灵能的多少（
a
i
a_i
ai非负表示这名高阶圣堂武士比在最佳状态下多余了
a
i
a_i
ai点灵能，
a
i
a_i
ai为负则表示这名高阶圣堂武士还需要
−
a
i
-a_i
−ai点灵能才能到达最佳战斗状态）。
现在系统赋予了你的高阶圣堂武士一个能力：传递灵能。每次你可以选择一个
i
∈
[
2
,
n
−
1
]
iin [2,n-1]
i∈[2,n−1]，若
a
i
≥
0
a_i≥0
ai≥0则其两旁的高阶圣堂武士，也就是
i
−
1
,
i
+
1
i-1,i+1
i−1,i+1这两名高阶圣堂武士会从
i
i
i这名高阶圣堂武士这里各抽取
a
i
a_i
ai点灵能；若
a
i
<
0
a_i<0
ai<0则其两旁的高阶圣堂武士，也就是
i
−
1
,
i
+
1
i-1,i+1
i−1,i+1这两名高阶圣堂武士会给
i
i
i这名高阶圣堂武士
−
a
i
-a_i
−ai点灵能。
形式化来讲就是
a
i
−
1
+
=
a
i
,
a
i
+
1
+
=
a
i
,
a
i
−
=
2
a
i
a_{i-1}+=a_i,a_{i+1}+=a_i,a_i−=2a_i
ai−1+=ai,ai+1+=ai,ai−=2ai。
灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为
m
a
x
i
=
1
n
∣
a
i
∣
max_{i=1}^n|a_i|
maxi=1n∣ai∣，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武士的不稳定度最小。
【输入格式】
本题包含多组询问。输入的第一行包含一个正整数
T
T
T表示询问组数。
接下来依次输入每一组询问。
每组询问的第一行包含一个正整数
n
n
n，表示高阶圣堂武士的数量。
接下来一行包含
n
n
n个数
a
1
,
a
2
,
…
,
a
n
a_1,a_2,dots ,a_n
a1,a2,…,an。
【输出格式】
输出
T
T
T行。
每行一个整数依次表示每组询问的答案。
【数据范围】
1
≤
T
≤
3
1≤T≤3
1≤T≤3
3
≤
n
≤
300000
3≤n≤300000
3≤n≤300000
∣
a
i
∣
≤
1
0
9
|a_i|≤10^9
∣ai∣≤109
【输入样例1】
3 3 5 -2 3 4 0 0 0 0 3 1 2 3
【输出样例1】
3 0 3
【输入样例2】
3 4 -1 -2 -3 7 4 2 3 4 -8 5 -1 -1 6 -1 -1
【输出样例2】
5 7 4
【分析】
假设 s s s为数组 a a a的前缀和，那么每次进行操作时： a i − 1 + = a i a_{i-1}+=a_i ai−1+=ai，也就是 s i − 1 s_{i-1} si−1变成了 s i s_i si； a i − = 2 a i a_i-=2a_i ai−=2ai，其中有一个 a i a_i ai加到了 a i + 1 a_{i+1} ai+1上，也就是 s i s_i si变成了 s i − 1 s_{i-1} si−1； s i + 1 s_{i+1} si+1不变。因此每次操作会交换 s i − 1 s_{i-1} si−1和 s i s_i si。
我们需要求的是 m a x ( ∣ a i ∣ ) max(|a_i|) max(∣ai∣)的最小值，也就是 m a x ( ∣ s i − s i − 1 ∣ ) max(|s_i-s_{i-1}|) max(∣si−si−1∣)的最小值，那么假设 s s s是有序的，显然 m a x ( ∣ s i − s i − 1 ∣ ) max(|s_i-s_{i-1}|) max(∣si−si−1∣)就是最小的，但是本题第一个和最后一个武士不能传输灵能，也就是 s 0 s_0 s0和 s n s_n sn的位置是不能变的，这样就产生了新的问题。我们最终得到的一个序列并不一定是单调的，所以接下来我们就要通过一系列操作解决不单调序列的问题。
通过画图可知一个有两个拐点的曲线重叠部分最小时，单调部分最多，而一个曲线符合下列两种情况时便符合最优解的要求：
- 左端点小于右端点，即要求
s
0
<
s
n
s_0
可以画图理解一下，如下图所示，显然蓝线比红线更优，因为红线中间那段重复走了三遍，而蓝线只走过一次。
【代码】
#include#include #include #include using namespace std; typedef long long LL; const int N = 300010; LL s[N], f[N]; bool st[N]; int n; int main() { int T; cin >> T; while (T--) { cin >> n; s[0] = 0;//多组测试数据注意初始化 memset(st, false, sizeof st); for (int i = 1; i <= n; i++) { cin >> s[i]; s[i] += s[i - 1]; } LL s0 = s[0], sn = s[n];//注意要用LL if (s0 > sn) swap(s0, sn); sort(s, s + n + 1); for (int i = 0; i <= n; i++) if (s[i] == s0) { s0 = i; break; }//找出s[0]在排序后的位置 for (int i = n; i >= 0; i--) if (s[i] == sn) { sn = i; break; }//找出s[n]在排序后的位置 int l = 0, r = n; for (int i = s0; i >= 0; i -= 2)//从s[0]先向最小值跳 f[l++] = s[i], st[i] = true; for (int i = sn; i <= n; i += 2)//从s[n]先向最大值跳 f[r--] = s[i], st[i] = true; for (int i = 0; i <= n; i++)//将没遍历到的剩余的s[i]遍历一遍 if (!st[i]) f[l++] = s[i]; LL res = 0; for (int i = 1; i <= n; i++) res = max(res, abs(f[i] - f[i - 1])); cout << res << endl; } return 0; }
