璟雯院

珺璟如晔,雯华若锦

用户工具

站点工具


icpc:problems:usaco23jan_moo_route_s
problems
名称Moo Route S
题目编号USACO23JAN_S3
题目链接luogu.com.cn/…
来源USACO
算法分类贪心
难易程度看懂题解

Moo Route S

想法

因为题目要求尽可能减少转弯,所以我们每次贪心能直走就直走,不能直走在转弯。

分类讨论:

右走:当下一位为0时就不再走了。

左走:当下一位是1,但是这一位不是1时,就需要拐弯。

3 1 1 5 5 5 1 1 1

这个例子中,向左走时,就只能走到第4位,这个位置就必须转弯了。

代码实现

#include<iostream>
using namespace std;
 
int main()
{
	int n;
	cin >> n;
	int line[n];
	for (int i = 0; i < n; ++i) 
		cin >> line[i];
 
	int x = 0;
	while(true)
	{
		while(x < n && line[x]){
			cout << 'R';
			line[x]--;
			x++;
		}
		x--;
 
		while(x >= 0 && line[x] == 1){
			cout << 'L';
			line[x]--;
			x--;
		}
		if(x == -1)break;
		while(x >= 0 && line[x] != 1){
			cout << 'L';
			line[x]--;
			x--;
		}
		x++;
	}
 
	return 0;
}
/app/www/public/data/pages/icpc/problems/usaco23jan_moo_route_s.txt · 最后更改: 2023/03/04 08:15 由 温婕莺