「HDU Multi 2021」[HDU 7075] Unfair contest

「题意」

给定两个长为 $n-1$ 的序列 $a$ 和 $b$,以及三个正整数 $s,t,h$。现在可以给 $a,b$ 分别插入一个正整数 $a_n$ 和 $b_n$(要求范围在 $[1,h]$),补成 $n$ 个数。

定义一个序列的权值为删去最小的 $s$ 个数和最大的 $t$ 个数后,剩余 $n-s-t$ 个数之和。

现要求 $a$ 的权值要严格大于 $b$ 的权值,求 $\max(a_n-b_n)$,若无解则输出IMPOSSIBLE

$\sum{n}\leq 10^6,h\leq 10^9$

「链接」

7075

「分析」

$a_n$ 和 $b_n$ 共有 $9$ 类情况,分别是被作为较小值删除、被保留和被作为较大值删除,分别讨论即可。

复杂度 $O(n\log{n})$。

「参考代码」

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
/*
* @date:
* @source:
*/
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
#define fir first
#define sec second
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)x.size()
#define up(i, l, r) for (int i = l; i <= r; ++i)
#define dn(i, l, r) for (int i = l; i >= r; --i)
#define Trav(i, x) for (auto & i : x)
#define pb push_back
template<class T, class G> bool chkMax(T &x, G y) {
return y > x ? x = y, 1 : 0;
}
template<class T, class G> bool chkMin(T &x, G y) {
return y < x ? x = y, 1 : 0;
}

const int MAXN = 1e5 + 5;

int N, s, t, h;
int A[MAXN], B[MAXN];

void solve() {
cin >> N >> s >> t >> h;
for (int i = 1; i < N; ++i) cin >> A[i];
for (int i = 1; i < N; ++i) cin >> B[i];
sort(A + 1, A + N);
sort(B + 1, B + N);
ll suma1 = 0, suma2 = 0, sumb1 = 0, sumb2 = 0;
for (int i = t; i <= N - s - 1; ++i) { // erase left max{a} = A[t] min{a} = 1
suma1 += A[i];
sumb1 += B[i];
}
for (int i = t + 1; i <= N - s; ++i) { // erase right max{a} = h min{a} = A[N - s]
suma2 += A[i];
sumb2 += B[i];
}
int ans = INT_MAX;
if (suma1 > sumb1 && t) {
chkMin(ans, 1 - B[t]);
}
if (suma1 > sumb2 && s && t) {
chkMin(ans, 1 - h);
}
if (suma2 > sumb1 && s && t) {
chkMin(ans, A[N - s] - B[t]);
}
if (suma2 > sumb2 && s) {
chkMin(ans, A[N - s] - h);
}
ll suma3 = 0, sumb3 = 0;
for (int i = t + 1; i < N - s; ++i) {
suma3 += A[i];
sumb3 += B[i];
}
//cout << "pre" << ans << endl;
if (!t) {
A[0] = 1, B[0] = 1;
}
if (!s) {
A[N] = h, B[N] = h;
}
for (int i = t; i <= N - s; ++i) {
int tmp = suma3 + A[i] - sumb3 - 1;
if ((t && tmp < B[t]) || (!t && tmp < 1)) continue;
chkMax(tmp, 1);
chkMin(ans, A[i] - min(tmp, B[N - s]));
}
//cout << ans << endl;
for (int i = t; i <= N - s; ++i) {
int tmp = sumb3 + B[i] - suma3 + 1;
if ((s && tmp > A[N - s]) || (!s && tmp > h)) continue;
chkMax(tmp, 1);
if (chkMin(ans, tmp - B[i])) {
//cout << tmp << " " << B[i] << "\n";
}
}
//cout << ans << endl;
if (t) {
int x = suma1 - sumb3 - 1;
if (x >= B[t] || (!t && x >= 1)) chkMin(ans, 1 - min(B[N - s], x));
int y = sumb1 - suma3 + 1;
chkMax(y, 1);
if (y <= A[N - s]) chkMin(ans, y - B[t]);
}
if (s) {
int x = suma2 - sumb3 - 1;
if (x >= B[t] || (!t && x >= 1)) chkMin(ans, A[N - s] - min(B[N - s], x));
int y = sumb2 - suma3 + 1;
chkMax(y, 1);
if (y <= A[N - s]) chkMin(ans, y - h);
}
if (ans == INT_MAX) cout << "IMPOSSIBLE\n";
else cout << ans << endl;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int Case;
cin >> Case;
while (Case--) solve();
return 0;
}