首页 > 试题广场 >

送外卖

[编程题]送外卖

热度指数：279 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

n 个小区排成一列，编号为从 0 到 n-1 。一开始，美团外卖员在第0号小区，目标为位于第 n-1 个小区的配送站。
给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ，在每个小区 i 里你有两种选择：
1) 选择a：向前 a[i] 个小区。
2) 选择b：向前 b[i] 个小区。

把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中，字典序最小的字符串。如果做出某个选择时，你跳出了这n个小区的范围，则这个选择不合法。
• 当没有合法的选择序列时，输出 “No solution!”。
• 当字典序最小的字符串无限长时，输出 “Infinity!”。
• 否则，输出这个选择字符串。

字典序定义如下：串s和串t，如果串 s 字典序比串 t 小，则
• 存在整数 i ≥ -1，使得∀j，0 ≤ j ≤ i，满足s[j] = t[j] 且 s[i+1] < t[i+1]。
• 其中，空字符 < ‘a’ < ‘b’。

输入描述:

输入有 3 行。

第一行输入一个整数 n (1 ≤ n ≤ 10^5)。

第二行输入 n 个整数，分别表示 a[i] 。

第三行输入 n 个整数，分别表示 b[i] 。

−n ≤ a[i], b[i] ≤ n

输出描述:

输出一行字符串表示答案。

示例1

输入

7
5 -3 6 5 -5 -1 6
-6 1 4 -2 0 -2 0

输出

abbbb

算法知识视频讲解

VisStu

分析一下题目的要求，字典序最小，也就是尽量能选a就选a，除非选a到不了终点，我们才选b。

如果当前位置选a会一直打转（进入循环），而选b可以抵达终点，我们仍然会选a。

因为两种方案：

aaaab

aaaaaab

方案二多打转了几次，它的字典序就比方案一的要小了（换句话说就是如果你先选b，你就输了）。

即打转次数越多，字典序就越小。但打转次数可以无限次，所以这时要输出"Infinity!"。

（那么有没有更短些的路径呢，比如aaaa就可以抵达，而不用aaaab这样？）

（大兄弟不可能的，同一个位置选同一个方案只能到同一个目的地啊，大家前面都是4个a，不可能谁要多走个b的）

具体怎么处理呢：

根据一开始的数据可以获取小区之间的路径（注意是单向的），用邻接矩阵或者其他什么的存一存，从终点开始广搜一遍，只要是经过的点都标记一下，代表从这个点出发，是存在路径能够抵达终点的。（如果标记完发现，起点没标记，那说起点->终点是没路的）。

然后从起点开始正向搜一遍，只要选a后抵达位置拥有标记（即能抵达终点）的，那我们就选a方法，否则选b方法。

这样的路径是唯一的，中间不会出现岔路，搜索过程中，如果你发现走到以前走过的点上，那说进入循环了，退出去输个" Infinity!"即可，

如果走到终点了，那就直接输出结果。

发表于 2017-06-20 22:31:11 回复(0)

C/C++

r088r088

1. 使用递归遍历ab的所有可能组合

2. 值得注意的是，对于n个小区，如果递归深度大于n-1，则表明发生了循环

说明：比如一条路的长度为123456，如果没有循环，则答案最大长度为5，比如从1到2， 2到3，到4，到5。假如循环，则长度必然大于5.

另外，走过的路径要封死，即将遍历ab后仍无法得到解的点的参数置为n+1

答的时候因为超时修改了太多次，事实上只完成上述一条即可

#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <set>
#include <algorithm>

using namespace std;
vector<int> a, b;

void calcAnsRe(const int &n, int pos, string &ans, int stop,
	bool &ok, string &answerS, bool &loop, bool &ansLoop, vector<int> &path, int &loopPos) {
	if (ok)	return;
	if (pos < 0 || pos >= n)	return;
	if (pos == n - 1)
	{
		answerS = ans;
		ok = true;
		if (loop)	ansLoop = true;
		return;
	}
	if (stop == 0)	return;
	if (!answerS.empty() && answerS <= ans)	return;

	if (find(path.begin(), path.end(), pos) != path.end()) {
		loop = true;
		loopPos = pos;
		return;
	}

	if (a[pos] != n + 1 && a[pos] + pos != loopPos)
	{
		ans += "a";
		path.push_back(pos);
		calcAnsRe(n, pos + a[pos], ans, stop - 1, ok, answerS, loop, ansLoop, path, loopPos);
		if (!ans.empty())	ans.pop_back();
		if (!path.empty())	path.pop_back();
	}
	if (b[pos] != n + 1 && b[pos] + pos != loopPos)
	{
		ans += "b";
		path.push_back(pos);
		calcAnsRe(n, pos + b[pos], ans, stop - 1, ok, answerS, loop, ansLoop, path, loopPos);
		if (!ans.empty())	ans.pop_back();
		if (!path.empty())	path.pop_back();
	}
	a[pos] = n + 1;
	b[pos] = n + 1;
	if (find(path.begin(), path.end(), loopPos) == path.end())
	{
		loop = false;
		loopPos = -1;
	}
}

int main() {
	int n;
	while (cin >> n) {
		string answerS;
		a.resize(n);
		b.resize(n);
		string tmp;
		bool ok = false, loop = false, ansLoop = false;
		vector<int> path;
		int atmp, btmp, loopPos = -1;
		if (n == 1)
		{
			cout << "" << endl;
			continue;
		}
		for (size_t i = 0; i < n; i++) {
			scanf("%d", &a[i]);
			atmp = a[i] + i;
			if (atmp < 0 || atmp >= n)
				a[i] = n + 1;
		}
		for (size_t i = 0; i < n; i++) {
			scanf("%d", &b[i]);
			btmp = b[i] + i;
			if (btmp < 0 || btmp >= n)
				b[i] = n + 1;
		}
		//for (size_t i = 0; i < n; i++)
		//{
		//	atmp = a[i];
		//	btmp = b[i];
		//	if (atmp != n + 1
		//		&& a[atmp + i] == n + 1
		//		&& b[atmp + i] == n + 1)
		//		a[i] = n + 1;
		//	if (btmp != n + 1
		//		&& a[btmp + i] == n + 1
		//		&& b[btmp + i] == n + 1)
		//		b[i] = n + 1;
		//}
		calcAnsRe(n, 0, tmp, n, ok, answerS, loop, ansLoop, path, loopPos);
		if (answerS.empty())
		{
			cout << "No solution!" << endl;
			continue;
		}
		else
		{
			if (ansLoop || answerS.size() > n - 1)
			{
				cout << "Infinity!" << endl;
				continue;
			}
			else	cout << answerS << endl;
		}
	}
}

编辑于 2017-06-27 07:44:16 回复(2)

嘛德啥都不会

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 0x3f3f3f3f;
const int N  = 1e5+10;
int n;
vector<int>T[N];
vector<int>G[N];
int st[N],sd[N];
char pre[N];
int idx;
int bfs1(int u)
{
	queue<int>q;
	q.push(u);
	st[u]=1;
	while(q.size())
	{
		auto t = q.front();
		q.pop();
		for(int i=0;i<G[t].size();i++)
		{
			int a = G[t][i];
			if(st[a]||a<0||a>n-1)continue;
			st[a]=1;
			q.push(a);
		}
	}
	return -1;
}
int bfs2(int u)
{
	queue<int>q;
	q.push(u);
	while(q.size())
	{
		auto t = q.front();q.pop();
		sd[t] = 1;
		int a = T[t][0],b=T[t][1];
		if(st[a]&&a>=0&&a<n)
		{
			if(sd[a])return -1;
			if(a==n-1)return 1;
			q.push(a);
			pre[idx] = 'a';
		}
		else if(st[b]&&b>=0&&b<n)
		{
			if(sd[b])return -1;
			if(b==n-1)return 1;
			q.push(b);
			pre[idx] = 'b';
		}
		idx++;
	}
	return 1;
}




signed main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		T[i].push_back(i+x);
		G[i+x].push_back(i);
	}
	for(int i=0;i<n;i++)
	{
		int x;
		cin>>x;
		T[i].push_back(i+x);
		G[i+x].push_back(i);
	}
	bfs1(n-1);
	int t = 1;
	// for(int i=0;i<n;i++){
		// for(int j=0;j<=1;j++){
			// cout<<T[i][j]<<" ";
			// }
			// cout<<endl;
			// }
	if(st[0])t = bfs2(0);
	else cout<<"No solution!";
	if(t==-1)cout<< "Infinity!";
	else
	{
		for(int i=0;i<idx;i++)
		{
			cout<<pre[i];
		}
	}
	
	return 0;
}

过90，求助/哭

发表于 2022-12-30 15:22:00 回复(0)

C/C++

cyhhao

这一组测试用例是不是有问题？

测试用例:
182
50 91 71 -87 70 -121 1 41 97 69 55 22 178 -32 1 -48 95 65 46 -102 82 -155 81 -95 134 73 -174 0 175 -93 82 82 -177 180 123 -132 28 -26 -28 127 -9 72 105 163 -103 -49 -98 131 58 117 22 -94 92 -168 128 19 15 23 -125 -12 -136 -9 -65 -36 99 -55 67 6 -167 9 96 -143 76 -143 28 91 -79 27 -32 -49 -44 158 113 -77 15 113 131 8 -161 38 70 91 -70 -148 -89 -49 -175 44 110 20 170 135 -17 -133 56 -102 -65 -45 -13 48 92 -33 -14 -87 -174 -37 16 51 142 -50 -91 -26 16 -181 20 -176 -55 18 6 -8 71 -114 65 -33 -36 -77 -125 121 79 13 110 -138 -115 -160 -81 -78 137 -141 -139 3 -7 -27 -80 -118 -7 62 -44 111 19 -59 -126 16 120 -53 -127 -95 -82 25 -14 176 40 -143 169 98 -122 52 55 171 -70 -13 -142 132
155 180 -18 128 -56 44 59 6 -16 108 -111 152 -139 34 37 110 -55 -58 -152 75 145 -168 122 10 138 -37 116 126 0 -124 1 180 -31 -13 4 54 -143 97 -157 52 22 -111 -45 -46 -25 -39 89 158 -91 79 9 -87 -113 71 -60 -161 151 46 -76 42 99 165 -6 -19 -57 -51 -143 88 148 119 -81 80 102 -77 -35 -6 -162 -144 -8 -120 -65 65 79 103 -52 -6 75 5 -106 105 -83 -84 40 -97 -1 56 -27 52 78 -44 -21 -93 -112 -87 -138 121 -46 -136 171 44 71 2 46 91 -41 -88 53 40 -78 30 27 -113 -65 94 180 -3 170 181 -48 69 15 -175 -164 -59 2 34 -138 -95 18 45 175 46 -13 93 99 -170 141 77 -20 15 89 -99 -58 144 -112 -13 -52 -86 -47 -100 109 -129 36 180 -131 178 -25 -178 -111 -136 179 -33 13 -64 81 70 -56 -38 129 0 -151 77

对应输出应该为:
Infinity! 
你的输出为:
aaaaaabbbbaabaaabbbaaaaaaabaababaaabbbaabaaabbbabaaaaaabababaabbbb

是有最优解的啊？为什么判断为Infinity？
求教~

发表于 2017-06-18 22:51:03 回复(6)