CF578E Walking

Codeforces 578E Summary

Table of Contents

• 1. 题目大意
• 2. 解法
• 3. 代码

1 题目大意

给出一个只有'L''R'字符串 S，求一个排列 P 使得 S[P[i]]!=S[P[i+1]],最小化 P[i]>P[i+1]的位置个数。

2 解法

一个很直觉的想法是，直接贪心构造，枚举从'L'或'R'开始，每次往后走到下一个未走到的合法位置，否则就走到最左端的合法位置……

然而会有特殊情况（卡了半天……

我们发现往回连跳两次肯定是不优的，那么想个办法特判掉：设当前点颜色为 x，若下一个未走到的合法位置后没有为 x 的点，并且最左端的合法位置左边也没有为 x 的点，那么我们往左跳。

仔细想想这是为什么……

3 代码

#define DEBUG
#include <cstdio>
#include <cstring>

using namespace std;

const int maxn=100000;

int min(int a, int b) {
  return a<b ? a : b;
}

int max(int a, int b) {
  return a>b ? a : b;
}

class SegmentTree {
public:
  int v[4*maxn+1];

  void add(int o, int l, int r, int t, int tv) {
    if (l==r) {
      v[o]+=tv;
    } else {
      int mid=(l+r)/2;
      if (t<=mid) {
        add(o*2, l, mid, t, tv);
      } else {
        add(o*2+1, mid+1, r, t, tv);
      }
      v[o] = v[o*2]+v[o*2+1];
    }
  }

  int getMin(int o, int l, int r, int tl, int tr) {
    if (tl>tr || !v[o]) {
      return 0;
    }
    int mid=(l+r)/2;
    if (l==r) {
      return l;
    } else if (l==tl && r==tr) {
      if (v[o*2]) {
        return getMin(o*2, l, mid, l, mid);
      } else {
        return getMin(o*2+1, mid+1, r, mid+1, r);
      }
    } else {
      if (tl<=mid) {
        int t=getMin(o*2, l, mid, tl, min(tr, mid));
        if (t) return t;
      }
      if (tr>mid) {
        int t=getMin(o*2+1, mid+1, r, max(tl, mid+1), tr);
        if (t) return t;
      }
      return 0;
    }
  }
};

int now[maxn+1];

int solve(int n, bool a[], int x) {
  static SegmentTree pos[2];
  for (int i=1; i<=n; i++) {
    pos[a[i]].add(1, 1, n, i, 1);
  }
  int ans=0;
  for (int i=1, o=0; i<=n; i++, x=!x) {
    int p=pos[x].getMin(1, 1, n, o+1, n), q=pos[x].getMin(1, 1, n, 1, o-1);
    if (p && !pos[!x].getMin(1, 1, n, p+1, n) && q && !pos[!x].getMin(1, 1, n, 1, q-1)) {
      ans++;
      o = q;
    } else if (p) {
      o = p;
    } else {
      ans++;
      o = q;
    }
    pos[x].add(1, 1, n, o, -1);
    now[i] = o;
  }
  return ans;
}

int main() {
#ifdef DEBUG
  freopen("src.in", "r", stdin);
  freopen("src.out", "w", stdout);
#endif

  static char s[maxn+2];
  static int cnt[2];
  static bool a[maxn+1];
  int n;
  scanf("%s", s+1);
  n = strlen(s+1);
  for (int i=1; i<=n; i++) {
    a[i] = s[i]=='R';
    cnt[a[i]]++;
  }

  static int ans[maxn+1];
  ans[0] = n+1;
  if (cnt[0]>=cnt[1]) {
    int t=solve(n, a, 0);
    if (ans[0]>t) {
      ans[0] = t;
      memcpy(ans+1, now+1, n*sizeof(int));
    }
  }
  if (cnt[1]>=cnt[0]) {
    int t=solve(n, a, 1);
    if (ans[0]>t) {
      ans[0] = t;
      memcpy(ans+1, now+1, n*sizeof(int));
    }
  }
  printf("%d
", ans[0]);
  for (int i=1; i<=n; i++) {
    printf("%d ", ans[i]);
  }

  fclose(stdin);
  fclose(stdout);
  return 0;
}

Author: lutts

Created: 2020-09-17 四 22:26

Validate