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

原创于 2024-04-08 12:26:39 发布 · 粉丝可见 · 458 阅读 · 11 · 2 · 本内容遵循CC 4.0 BY-SA版权协议版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/137503347

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

样例：

`cobol<br/>4 3<br/>1 2 3 4<br/>`

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 
		// 说明我们可以直接选取，最少操作数为 1
		if(x % p == 0)	
		{
			cout << 1 << endl;
			return ;
		}
	}
	
	// 开始 BFS 搜索
	BFS();
	
	cout << ans[0] << endl;
}