2020 Petrozavodsk Winter Camp Day 5 L

Problem L. Wizards Unite

Statement

给 $1$ 把金钥匙(可多次使用的钥匙),$k$ 把银钥匙(只能用一次)。给 $n$ 个箱子,每个箱子有一个打开所需时间 $t_i$(跟钥匙类型无关)。一把钥匙同时只能开一个箱子,问打开所有箱子所需的最小总时间。有 $z$ 组测试数据。

$0 \leq k < n \leq 10^5$

$0 \leq t_i \leq 10^9$

$\sum n \leq 10^6$

Solution

本场最简单的题。

不失一般性,我们认为所有箱子按 $t_i$ 排升序。显然方案只能是 $k$ 把银钥匙都用来开一个箱子,金钥匙开其他所有箱子,而答案就是以下两者中的较大值:用银钥匙的箱子中耗时最长的一个的耗时;金钥匙开其他所有箱子的耗时之和。

注意到答案无论如何也不可能小于 $t_n$,也就是说用银钥匙开 $t_n$ 箱子一定不会浪费时间。那么为了令金钥匙耗时之和尽可能小,实际上 $k$ 把银钥匙开的就是最右边的 $k$ 个箱子,于是答案就很显然了。时间复杂度 $O(n \log n)$。

我读的,读完第一反应居然是二分答案找一个分界点使得银钥匙开的是这个分界点左边的 $k$ 个……要说的话虽然更慢(我写的是 $O(n \log^2 n)$……)但是结果也是对的,但我一个大于写成了大于等于交了一发 WA……签到题都 WA,很惭愧……

下面的代码还是赛中交的二分答案版本,反正正解上面说的很清楚了,也很简单,懒得再写了。

Code (By Nanako)

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
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#define all(v) (v).begin(), (v).end()
#define unq(v) (v).erase(unique(all(v)), (v).end())
#define ii int, int
#define li int, int
#define ll2 ll, ll
#define vec vector
#define pii pair <int, int>
#define pli pair <ll, int>
#define pll2 pair <ll, ll>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define MULTI int T; cin >> T; while(T--)
#define sqr(x) ((x) * (x))
#define test cerr << '!' << endl;
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

int main0 ();
int main () {
#ifndef ONLINE_JUDGE
freopen("C:\\Users\\98497\\Desktop\\code\\file.in", "r", stdin);
#endif
ios::sync_with_stdio(false);
clock_t start, end;
// start = clock();
main0();
// end = clock();
// cout << (end - start) << endl;
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
return 0;
}

const int dx[8] = {0, 1, -1, 0, 1, 1, -1, -1};
const int dy[8] = {1, 0, 0, -1, 1, -1, -1, 1};
const int N = 2e5 + 5;
const int M = 1e5;
const int INF = 0x3f3f3f3f;
const ll INFF = 0x3f3f3f3f3f3f3f3f;
const int mod = 998244353;
const double eps = 1e-6;
const double Pi = acos(-1.0);

ll a[N];

int main0 () {
MULTI {
int n, k;
cin >> n >> k;
ll sum = 0;
for (int i = 1;i <= n;++i) {
cin >> a[i];
sum += a[i];
}
sort(a + 1, a + n + 1);

ll l = 0, r = sum;
while (l <= r) {
ll mid = (l + r + 1) / 2;
int pos = upper_bound(a + 1, a + n + 1, mid) - a; pos--;
ll silver = 0;
for (int i = max(1, pos - k + 1);i <= pos;++i) silver += a[i];
//cout << l << ' ' << r << ' ' << mid << ':' << pos << ' ' << silver << endl;
if (sum - silver > mid) l = mid + 1;
else r = mid - 1;
}
cout << l << endl;
}
}