Codeforces 789E

发表于 |

题目

给K种浓度分别为$\frac{a_i}{1000}$的饮料，要求每种饮料用整数升，兑出浓度为$\frac{N}{1000}$的饮料。求最少要用几升饮料。

数据范围

$0\leq n\leq 1000,1\leq k\leq 10^6$

$0\leq ai \leq 1000,a_i \in Z$

做法

由鸽巢原理，不同浓度的饮料最多有1001种。
令K为不同浓度的种数。设每种饮料用了xi升，则有
$$
\frac{\sum_{i=1}^Kx_i\times \frac{a_i}{1000}}{\sum_{i=1}^Kx_i}=\frac{N}{1000}
$$
化简后为
$$
\sum_{i=1}^Kx_i\times (N−a_i)=0
$$
原问题就规约为：从集合${N-a_i}$中取最少的数（每个数可以取任意次），使得他们的和为0。

我们以和为顶点，根据集合中的数来连边（若集合中有数字$N−a_i$，则从和$s$到和$s+(N−a_i)$连边）。

问题就规约成：找从0开始，以0结束的最小环的长度。BFS即可。

优化：由N和$a_i$的范围可知：$−1000\leq N−a_i\leq 1000$。所以若存在起点、终点为0的环，则我们可以通过重构环上边的顺序，使得每次经过一条边后，和都在[−1000,1000]的范围内。因此我们建图时，和的范围在[−1000,1000]内即可。

时间复杂度：$O(E)=O(2001\times max(1001,K))$

代码

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
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1e3 + 5;
const int offset = 1e3;
const int INF = 0x3f3f3f3f;
int N, K;
bool has[MAX_N];
int d[MAX_N * 2];
vector<int> G[MAX_N * 2];
int bfs(int s)
{
  queue<int> que; que.push(s);
  memset(d, 0x3f, sizeof d);
  d[s] = 0;
  while (!que.empty()) {
    int v = que.front(); que.pop();
    for (int i = 0; i < (int)G[v].size(); ++i) {
      int u = G[v][i];
      if (u == s) {
        return d[v] + 1;
      } else if (d[u] == INF) {
        d[u] = d[v] + 1;
        que.push(u);
      }
    }
  }
  return INF;
}
int main()
{
  cin >> N >> K;
  for (int i = 0; i < K; ++i) {
    int a; scanf("%d", &a);
    has[a] = 1;
  }
  for (int sum = -1000; sum <= 1000; ++sum) {
    for (int a = 0; a <= 1000; ++a) {
      if (has[a]) {
        int nxt = N - a + sum;
        if (-1000 <= nxt && nxt <= 1000) {
          G[sum + offset].push_back(nxt + offset);
        }
      }
    }
  }
  int ans = bfs(0 + offset);
  if (ans == INF) {
    puts("-1");
  } else {
    printf("%d\n", ans);
  }
  return 0;
}