[ICPC2021 Nanjing R] Windblume Festival

单击此处下载原神

题面翻译

给一个长度为 $n$ 环形整数序列 $a$, 每次操作可以任意选择一个下标 $x$，令 $ a_x = a_x - a_{(x\bmod n)+1}$，之后移除 $a_{(x\mathrm{mod}n)+1}$。

最后会剩下一个元素，要求最大化这个元素。

数据范围 $1\le n\le 10^6,-10^9\le a_i\le 10^9$。

题目描述

The Windblume Festival in Mondstadt is coming! People are preparing windblumes for Barbatos and for those they love and adore. The Windblume Festival is also an opportunity to improve the relationships people have.

During the festival, a famous game will be played every year, invented by Jean, the Acting Grand Master of the Knights of Favonius. In the game, $n$ players numbered from $1$ to $n$ stand in a circle, each holding an integer with them. Each turn, one player will be removed. The game will end when there is only one player left.

For each turn, let $k$ be the number of players remaining and $a_i$ be the integer player $i$ holds. Two adjacent players, $x$ and $(x\mathrm{mod}k+1)$ are selected and player $(x\mathrm{mod}k+1)$ is removed from the game. Player $x$’s integer will then change from $a_x$ to $(a_x-a_{x\mathrm{mod}k+1})$. Player $y$ in this turn will become player $(y-1)$ in the next turn for all $x<y\le k$, though the integer they hold will not change.

Jean wants to know the maximum possible integer held by the last remaining player in the game by selecting the players in each round optimally.

输入格式

There are multiple test cases. The first line of the input contains one integer $T$ indicating the number of test cases. For each test case:

The first line contains one integer $n$ ($1\le n\le 10^6$) indicating the initial number of players.

The next line contains $n$ integers $a_i$ ($-10^9\le a_i\le 10^9$) where $a_i$ is the integer held by player $i$ at the beginning.

It is guaranteed that the sum of $n$ of all test cases will not exceed $10^6$.

输出格式

For each test case output one line containing one integer indicating the maximum possible integer.

样例 #1

样例输入 #1

5
4
1 -3 2 -4
11
91 66 73 71 32 83 72 79 84 33 93
12
91 66 73 71 32 83 72 79 84 33 33 93
13
91 66 73 71 32 83 72 79 84 33 33 33 93
1
0

样例输出 #1

10
713
746
779
0

提示

For the first sample test case follow the strategy shown below, where the underlined integers are the integers held by the players selected in each turn.

{ 1 ‾ , − 3 , 2 , − 4 ‾ } \{\underline{1}, -3, 2, \underline{-4}\} {1​,−3,2,−4​} (select $x=4$) $\to$ { − 3 , 2 , − 5 ‾ } \{-3, \underline{2, -5}\} {−3,2,−5​} (select $x=2$) $\to$ { − 3 , 7 ‾ } \{\underline{-3, 7}\} {−3,7​} (select $x=2$) $\to$ { 10 } \{10\} {10}.

$以上来自$原神$洛谷$

解题思路

我们先列出 3 种情况：只有负数，只有正数，正负数都有。

• 只有负数：以 $-11,-4,-5,-45$ 为例，发现得数最大为： $57$。
• 只有正数：以 $11,4,5,45$ 为例，发现得数最大为： $57$。
• 正负数都有：以 $-11,4,-5,45$ 为例，发现得数最大为： $65$。

我们发现，如果 $n$ 个数中正负数都有，输出的值即为所有数的绝对值之和；如果 $n$ 个数中只有正数或负数，那输出的数为所有数的绝对值之和，减去最小的绝对值的两倍。

说得简单一点，就是模拟。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Maxn = 1e6 + 10;
int T, n, a[Maxn];
int minn = INT_MAX, sum1, sum2;
int ans;
inline void solve() {minn = INT_MAX, sum1 = sum2 = 0;ans = 0;cin >> n;if (n == 1) {cin >> a[0];cout << a[0] << endl;return;}for (int i = 1; i <= n; i++) {cin >> a[i];}bool flag = 1;for (int i = 1; i <= n; i++) {if (a[i] > 0) {flag = 0;break;}}if (flag) {for (int i = 1; i <= n; i++) {a[i] = abs(a[i]);}}for (int i = 1; i <= n; i++) {minn = min(minn, a[i]);sum1 += a[i];sum2 += abs(a[i]);}if (minn < 0) {ans = sum2;} else {ans = sum1 - minn * 2;}cout << ans << endl;
}
inline void work() {cin >> T;while (T--) {solve();}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);work();return 0;
}