本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-06-05 15:08:26

我不理解为什么题解区所有做法都需要枚举 $[-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;
}