Codeforces Round 2124 (Div. 1+2)
Codeforces Round 2124 (Div. 1+2)
可惜，感觉很多时候时间在找思路上面和证明思路上面，找思路还是有点慢了。
我们只需要找到一个相邻的逆序对即可，有则可以把所有其他数都删完。若没有这样的逆序对，则说明原序列里所有数已经是递增的了，此时不管怎么删，都不会改变这些数的相对顺序，因此无解。
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
| #include <iostream>
#include <vector>
void run() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; ++i) { std::cin >> a[i]; }
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (a[i] > a[j]) {
std::cout << "YES\n2\n";
std::cout << a[i] << " " << a[j] << "\n";
return;
}
}
}
std::cout << "NO\n";
}
int main(int argc, char *argv[]) {
int T;
std::cin >> T;
while (T--) run();
return 0;
}
|
首先，我们可以又一个大致的想法：把 0 尽可能放前面，这样后面的 prefix min 就都是 0，大概率能更小一点。
所以，我们贪心地考虑前 3 个位置。如果 a1>a2，则令 (i,j)=(1,2)，总和为 a1+a2；若 a1<a2，则令 (i,j)=(2,3)，总和为 a1+a1，于是此时的总和最小可以达到
a1+min(a1,a2)而 S≥a1+min(a1,a2)，所以这就是最小。