Codeforces 732E Sockets

发表于 分类于 Disqus：

链接

传送门

题意

有\(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;
}
相关文章