小红不想做完全背包（hard）（BFS最少操作）

本题链接：登录—专业IT笔试面试备考平台_牛客网

样例：

输入
`4 3 1 2 3 4`

输出
1

思路：

根据题意，要求拿去物品数量的最小值，也可以看作是最少操作拿取的次数。

所以我们应该联想到 BFS 搜索，以后遇到最小值、最少值...这些，再看到数据范围，可以考虑一下 BFS。

这里我们定义一个 Pair 值，其中一个是操作次数，另一个是操作结果，随后用一个 ans[] 存储各个操作结果的次数。

ans [ 下标 ] = 值这里 ans 下标表示操作结果，值表示我们操作次数。

当我们操作结果 ans[0] 出现后，说明我们的选择次数有结果了，输出答案即可。

代码详解如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();signed main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;
//	cin >> _t;while (_t--){solve();}return 0;
}
// 这里 的 PII x 表示操作次数， y 表示 操作结果
using PII = pair<int,int>;
int ans[N];	// 记录操作结果最小值
int arr[N];	// 存储对应价值数组
int n,p;
inline void BFS()
{queue<PII>q;q.emplace(PII(0,0));	// 初始时都没有操作while(q.size()){// 拿出计划操作的其中一次PII now = q.front();q.pop();for(int i = 1;i <= n;++i){// 如果操作这次有结果整除次数，我们纳入计划操作if(!ans[(now.y + arr[i]) % p]){ans[(now.y + arr[i]) % p] = now.x + 1;	// 累计操作次数q.emplace(PII(now.x + 1,(now.y + arr[i]) % p));	// 纳入操作次数}}if(ans[0]) return ;	// 如果出现整除为 0 的操作次数，那么该操作次数一定为最小值，结束搜索}
}
inline void solve()
{cin >> n >> p;for(int i = 1,x;i <= n;++i){cin >> x;arr[i] = x;// 当出现 一个数可以整除 p // 说明我们可以直接选取，最少操作数为 1if(x % p == 0)	{cout << 1 << endl;return ;}}// 开始 BFS 搜索BFS();cout << ans[0] << endl;
}