题解：CF788C The Great Mixing

· · 题解

我不理解为什么题解区所有做法都需要枚举 [-1000,1000]。

我实际测试，[0,1000] 就足够了。

这篇题解将主要说明为什么 [0,1000] 足够。

做法

首先，令 b_i = a_i -n，那么题目显然可以转化为，选择 k \gt 0 个下标 p_1,p_2,\cdots,p_k，使得 \sum\limits_{i=1}^k b_{p_i} = 0。

令 dis_i 表示总和为 i 需要选择的最少下标数量，那么，可以通过 bfs 来进行转移。

但是，可能的总和范围在 [-10^6,10^6] 之间，也就是说有 2\times 10^6 个编号在 [-10^6,10^6] 的点。

而每个点最多有 10^3 个连接的点，肯定爆炸了。

但是，事实上，只有编号 [0,10^3] 的点才是有效的，接下来证明为什么。

首先，枚举的总和范围在 [0,10^6]。

证明：已知最后总和为 0，所以，负数的绝对值总和是等于正数的绝对值总和的，重新排列累加顺序，先累加所有正数，再累加所有负数，就可以保证过程的总和非负。

接着，上界可以降低到 10^3。

证明：如果有某一步，总和超过了 10^3，但是已知的是最终总值小于等于 10^3，所以，必然存在一种方案，将当前的数和后面步骤某个数交换，使得当前这一步的绝对值小于等于 10^3。 

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(auto i=(a);i<=(b);i++)
#define REP(i,a,b) for(auto i=(a);i>=(b);i--)
#define FORK(i,a,b,k) for(auto i=(a);i<=(b);i+=(k))
#define REPK(i,a,b,k) for(auto i=(a);i>=(b);i-=(k))
#define pb push_back
#define mkpr make_pair
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
template<class T>
void ckmx(T& a,T b){
    a=max(a,b);
}
template<class T>
void ckmn(T& a,T b){
    a=min(a,b);
}
template<class T>
T gcd(T a,T b){
    return !b?a:gcd(b,a%b);
}
template<class T>
T lcm(T a,T b){
    return a/gcd(a,b)*b;
}
#define gc getchar()
#define eb emplace_back
#define pc putchar
#define ep empty()
#define fi first
#define se second
#define pln pc('\n');
#define islower(ch) (ch>='a'&&ch<='z')
#define isupper(ch) (ch>='A'&&ch<='Z')
#define isalpha(ch) (islower(ch)||isupper(ch))
template<class T>
void wrint(T x){
    if(x<0){
        x=-x;
        pc('-');
    }
    if(x>=10){
        wrint(x/10);
    }
    pc(x%10^48);
}
template<class T>
void wrintln(T x){
    wrint(x);
    pln
}
template<class T>
void read(T& x){
    x=0;
    int f=1;
    char ch=gc;
    while(!isdigit(ch)){
        if(ch=='-')f=-1;
        ch=gc;
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=gc;
    }
    x*=f;
}
const int maxn=1005;
int n,k;
bitset<maxn> ok;
int dis[maxn];
void bfs(){
    memset(dis,0x3f,sizeof dis);
    int inf=dis[0];
    queue<int> q;
    FOR(i,n,1000){
        if(ok[i])dis[i-n]=1,q.push(i-n);
    }
    while(!q.empty()){
        int u=q.front();
        q.pop();
        FOR(i,0,1000){
            if(ok[i]){
                int to=u+i-n;
                if(to>=0&&to<=1000){
                    if(dis[to]>dis[u]+1){
                        dis[to]=dis[u]+1;
                        q.push(to);
                    }
                }
            }
        }
    }
    if(dis[0]==inf)puts("-1");
    else printf("%d\n",dis[0]);
}
void solve(int id_of_test){
    read(n);
    read(k);
    FOR(i,1,k){
        int a;
        read(a);
        ok[a]=1;
    }
    bfs();
}
int main()
{
    int T;
    T=1;
    FOR(_,1,T){
        solve(_);
    }
    return 0;
}