【思维构造】Sequence Master—CF1806C

Sequence Master—CF1806C
参考文章

思路

很容易想到全由 $0$ 组成的数组 $q$ 一定是满足条件的。

当 $n=1$ 时，我们还可以构造数组 { x , x } \{x, x\} {x,x}，也是满足条件的。

当 $n=2$ 时，我们通过样例解释发现 { 2 , 2 , 2 , 2 } \{2, 2, 2, 2\} {2,2,2,2} 满足条件。
但通过样例输出发现这对于第三个样例并不是最优的，于是我们暴力输出 $n=2$ 的所有可行数组： { − 1 , − 1 , − 1 , 2 } \{-1, -1, -1, 2\} {−1,−1,−1,2}、 { 0 , 0 , 0 , 0 } \{0, 0, 0, 0\} {0,0,0,0}、 { 2 , 2 , 2 , 2 } \{2, 2, 2, 2\} {2,2,2,2}，发现了新的可行数组： { − 1 , − 1 , − 1 , 2 } \{-1, -1, -1, 2\} {−1,−1,−1,2}，第三个样例正是这种情况！

我们考虑为什么数组 { − 1 , − 1 , − 1 , 2 } \{-1, -1, -1, 2\} {−1,−1,−1,2} 时可行的，适当思考将其转化为： { − 1 , − 1 , − 1 , n } \{-1, -1, -1, n\} {−1,−1,−1,n}。我们对 { − 1 , − 1 , − 1 , . . . , n } \{-1, -1, -1,..., n\} {−1,−1,−1,...,n} 分析，发现在 $n$ 是偶数的时候这样的数组是满足条件的。

我们暂且贪心地认为以上分析包括了所有满足条件的数组，不存在遗漏。写代码发现可以 $AC$，那么我们的思路没有问题。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;

int n;
int a[2 * N];

void solve() {
	cin >> n;
	for (int i = 1; i <= 2 * n; i ++) {
		cin >> a[i];
	}
	sort(a + 1, a + 2 * n + 1);
	
	int res = 0;
	for (int i = 1; i <= 2 * n; i ++) {
		res += abs(a[i]);
	}
	if (n == 1) {
		res = min(res, a[2] - a[1]);
	}
	if (n == 2) {
		int sum = 0;
		for (int i = 1; i <= 4; i ++) {
			sum += abs(a[i] - 2);
		}
		res = min(res, sum);
	}
	if (n % 2 == 0) {
		int sum = abs(a[2 * n] - n);
		for (int i = 1; i < 2 * n; i ++) {
			sum += abs(a[i] - (-1));
		}
		res = min(res, sum);
	}
	
	cout << "         ";
	cout << res << "\n";
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52