【Codeforces 788C】The Great Mixing

http://codeforces.com/contest/788/problem/C

显然如果有两杯一样的酒，把它们当作同一杯就好了。所以k<=1e6毫无意义。

若选的x杯酒的浓度分别为a,b,c,..,z，则由题意得(a+b+c+...+z)/x=n*x，整理可得(a-n)+(b-n)+(c-n)+...+(z-n)=0。

于是问题就转化成了从所有ai-n中选x个数使得和为0，求x的最小值。

然后由我也不知道怎么证明，可知(a-n),(b-n),(c-n),...,(k-n)可以通过调整顺序使任意前缀和均≥0且≤1000，所以BFS+剪枝即可。相当于在一张1001个结点的稠密无权图上跑最短路，所以时间复杂度为O(1001²)。

#include <iostream>
#include <queue>
#define maxn 1005
using namespace std;
int n, m;
int dist[maxn];
bool exist[maxn];
queue<int> que;
int main()
{
    ios::sync_with_stdio(false);
    cin >> m >> n;
    int tmp;
    for (int i = 1; i <= n; i++)
    {
        cin >> tmp;
        exist[tmp] = true;
    }

    que.push(0);
    while (!que.empty())
    {
        int x = que.front();
        que.pop();
        for (int i = 0; i <= 1000; i++)
        {
            int w = x + i - m;
            if (exist[i] && w >= 0 && w <= 1000 && !dist[w])
            {
                que.push(w);
                dist[w] = dist[x] + 1;
                if (w == 0)
                {
                    cout << dist[0];
                    return 0;
                }
            }
        }
    }
    cout << -1;
    return 0;
}