[USACO23JAN] Moo Route S 题解

FFTotoro · 2023-01-31 20:14:09 · 题解

本题需要使用贪心算法。

考虑如何让转向的次数尽量少：在往一个方向走的时候，能走就走，最大限度地消耗完经过次数。

往右走的时候，策略十分简单——只要当前点的次数大于等于 2，那么就一定可以走（包括返程正好 2 次）。走过之后，这个点的次数减去 1。

往左走的时候，如果将要走到某个坐标时，这个坐标上的剩余次数大于等于 3，那么就可以放心地走过去——因为如果需要再回来消耗剩余的次数，次数绝对是足够的。但是如果这个点只剩下走过去的那仅有的一次机会，那就要分情况讨论了：

• 现在所在的点右边的点次数全部消耗完——反正不用再回去了，往左走；

• 右边的点次数没有消耗完——回到往右走的状态，因为如果往左走了就再也回不去了；

走过去后该点次数减 1。

实现时，如果次数没消耗完，就标记一下，往左走的时候看一下标记即可。

放代码：

/*
ID: CrowMatrix
TASK: Moo Route
LANG: C++
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
  ios::sync_with_stdio(false);
  int n,x=0; cin>>n;
  vector<int> a(n);
  for(auto &i:a)cin>>i;
  while(1){
    vector<bool> r(n+1); // 标记数组
    while(x<n){
      if(a[x]>=2)a[x]--,x++,cout<<'R'; // 还可以往右走
      else break; // 次数没了，不需要继续往右走
    }
    while(1){
      if(x<n&&(a[x]>1||r[x+1]))r[x]=true; // 右边还有没消耗完的次数
      if(x&&(!r[x]||a[x-1]>1))a[--x]--,cout<<'L'; // 可以往左走
      else break; // 还要回去
    }
    if(!x&&!r[0])break; // 走完了
  }
  return 0;
}