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 由 温婕莺