Codeforces Contest 788 problem C The Great Mixing —— 求一些无穷个数之和为0所需最少数

This way

题意；

给你n个数，每个数都有无穷多个，让你拿一些数使得这些数之和/数的个数=x

题解：

$\frac{a1+a2+..+ak}{k}=x$ $=>a1+a2+..+ak=x\ast k$ $=>(a1-x)+(a2-x)+...+(ak-x)=0$ 也就是说问你需要至少多少个数相加变成0. 容易理解，我们所需范围不过-1000到1000，之外再无作用，如果两个数相加>1000，之后再加一些负数=0，那么完全可以现在加负数，因为所有数<=1000，不会超出负数的范围。那么就用一个队列维护当前走到了哪些值即可。

#include<bits/stdc++.h> using namespace std; int dis[2005],num[1005]; queue<int>Q; int main() { int n,m,x; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) scanf("%d",&x),num[x]=1; for(int i=0;i<=2000;i++) dis[i]=1e9; dis[1000]=0; Q.push(1000); while(!Q.empty()) { int u=Q.front(); Q.pop(); for(int i=0;i<=1000;i++) { if(!num[i]) continue; if(u+i-n==1000&&dis[1000]==0) dis[1000]=dis[u]+1,Q.push(1000); if(u+i-n>=0&&u+i-n<=2000&&dis[u+i-n]>dis[u]+1) dis[u+i-n]=dis[u]+1,Q.push(u+i-n); } } printf("%d\n",dis[1000]==0?-1:dis[1000]); return 0; }