Codeforces 732E Sockets

链接

传送门

题意

有$n$个电脑,$m$个插口,每个电脑有一个需求能量$p_i(1 \leq p_i \leq 10^9)$,每个插口有一个输出能量$s_j(1 \leq s_j \leq 10^9)$。当$p_i=s_j$时,电脑$i$和插口$j$可以相连。使用适配器可以将插口的输出能量减少至原来的一半(向上取整)。输出最多能使多少组电脑和插口配对,和此时使用适配器的数量的最小值。

思路

用multiset存电脑。对于每个插口最多接$\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
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
#define X first
#define Y second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 200010;
int a[maxn], b[maxn];
pii s[maxn];
multimap<int, int> num;
multimap<int, int>::iterator it;
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
num.insert(make_pair(x, i));
}
for (int i = 1; i <= m; ++i) {
scanf("%d", &s[i].X);
s[i].Y = i;
}
sort(s + 1, s + m + 1);
int c = 0, u = 0;
for (int i = 1; i <= m; ++i) {
for (int j = 0; ; ++j) {
it = num.find(s[i].X);
if (it != num.end()) {
a[s[i].Y] = j;
b[it -> Y] = s[i].Y;
++c;
u += j;
num.erase(it);
break;
}
if (s[i].X == 1) {
break;
}
s[i].X -= s[i].X >> 1;
}
}
printf("%d %d\n", c, u);
for (int i = 1; i <= m; ++i) {
printf("%d ", a[i]);
}
puts("");
for (int i = 1; i <= n; ++i) {
printf("%d ", b[i]);
}
puts("");
return 0;
}

支付宝扫码领红包