$T$筆測資，
每筆測資給一$N$項數列，每次操作可以刪除兩項$a_i,a_j(i\ne j)$，並獲得$2(a_i+a_j-|a_i-a_j|)$價值，求最大可獲得價值。
$T\le 6,N\le 10^5, 1\le a_i\le 10^9$
假設$a_i<a_j$，那
$$2(a_i+a_j-|a_i-a_j|)=2[a_i+a_j-(a_j-a_i)]=4a_i$$
所以每次刪除可獲得比較小的那一項$\times 4$，因此我們要讓每對比較小的那一項越大越好。
考慮以下greedy策略：將第一大跟第二大配對，第三大跟第四大配對…第$2i-1$大跟第$2i$大配對。
排序後就能線性時間配對，時間複雜度$\mathcal{O}(TNlogN)$
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
|
#include <bits/stdc++.h>
using namespace std;
#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
signed main() {
EmiliaMyWife
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
vector<int> arr(n);
for(int i = 0; i < n; i++)
cin >> arr[i];
ll ans = 0;
sort(arr.begin(), arr.end(), greater<int>());
for(int i = 1; i < n; i+=2)
ans += 1LL*arr[i]*4;
cout << ans << '\n';
}
return 0;
}
|