The Great Mixing
题面翻译
有k种可乐,第i瓶可乐的CO2浓度是ai/1000,问要配置出浓度n/1000的可乐,最少需要几瓶可乐。
$0<=n<=1000$ , $1<=k<=10^{6}$ ,$0<=a_{i}<=1000$
输入:
第一行n和k。
第二行k个整数,第i个整数表示ai。
输出:
一行,表示最少需要几瓶,无解输出-1。
分析
题面翻译一点也不好看!
简单分析后发现这个千分之一可以直接去掉,考虑分子即可:
- 每个数可以用很多次,找出最少的数字,使它们的平均数为 $n$ 。
为了方便,其实可以将每一个数先减去 $n$ , 问题就简单一些了:
- 每个数可以用很多次,找出最少的数字,使它们的平均数为 $0$
我们可以用bfs搜索每一个数字出发到达 $0$ 的最短路径。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e3 + 5;
int n, k;
int tmp[2][2 * N];
int *tot = &tmp[0][N], *d = &tmp[1][N];
queue<int> q;
int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> k; memset(tmp[1], 0x3f, sizeof tmp[1]);
for (int i = 1, x; i <= k; i++)
cin >> x, tot[x - n]++;
for (int i = 0 - n; i <= 1000 - n; i++)
if (tot[i]) d[i] = 1, q.push(i);
while(q.size()){
int now = q.front(); q.pop();
for (int i = 0; i <= 1000; i++){
if (d[now + i - n] != 0x3f3f3f3f || d[i - n] != 1) continue;
d[now + i - n] = d[now] + 1, q.push(now + i - n);
}
}
cout << (d[0] == 0x3f3f3f3f ? -1 : d[0]);
return 0;
}
标签:tmp,int,CF788C,cin,ai,最少,可乐 From: https://www.cnblogs.com/genshin-player/p/18103663Written with StackEdit中文版.