自动搬运

查看原文

来自洛谷，原作者为

	lym2022 这个人很勤快，但不想留下什么

搬运于2025-08-24 23:14:36，当前版本为作者最后更新于2025-04-28 15:57:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

看到求最少步数自然的想到 bfs。

暴力 bfs，每走到一个点就 $O(n^2)$ 的查找能走到哪些点，搜到终点时输出步数，总复杂度 $O(n^3)$，肯定是会炸掉的，考虑优化。

注意到每次都要进行一个 $O(n^2)$ 的查找，考虑预处理，可以先 $O(n^2)$ 的算出所有走的步数的方案，排序后去重，在搜索时就可以只遍历去重后的数组，就可以将 $O(n^2)$ 的查找降到 $O(l)$，总复杂度为 $O(n\times l)$，就可以切掉了。

Code

#include<bits/stdc++.h>
using namespace std;

const int N = 4e6 + 5; 

int n,l,a[N],s,d[N],tot,cnt;

bool vis[N];

void bfs() {
	queue<pair<int,int> > q;     // first 是当前下标，second 是当前步数 
	q.push({1,0});          //初始下标为 1，步数为 0    
	while(!q.empty()) {
		int p = q.front().first;
		int step = q.front().second;
		q.pop();
		if(p == l) {          //如果到了 
			cout << step;     //输出步数 
			return;           //返回 
		}
		if(vis[p]) continue;  //走过了就跳过 
		vis[p] = true;        //标记走过 
		for(int i = 1;i<=cnt;i++) q.push({(d[i] + p - 1) % l + 1,step + 1});  //根据题目给的公式算出接下来会走到哪，步数加 1，入队 
	}
	cout << -1;         //不行就输出 -1 
}

int main() {
	cin >> n >> l;
	for(int i = 1;i<=n;i++) cin >> a[i];
	for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) d[++tot] = (a[i] + a[j]) % l;   //预处理可能走多少步 
	sort(d+1,d+1+tot);           //排序
	cnt = unique(d+1,d+1+tot) - d - 1;        //去重 
	bfs();
	return 0;
}

对你有帮助就点个赞吧 owo。