求条35ptsWA
查看原帖
求条35ptsWA
741633
Ryanhao楼主2024/10/16 20:10
#include <bits/stdc++.h>
using namespace std;

struct node {
  int64_t x;
  char op;
}a[214514];

int pid[214514];

int64_t __30pts(int s, int e) {
  int b1 = -1,b2 = -1,r1 = -1,r2 = -1;
  for (int i = s; i <= e; i++) {
    if (a[i].op == 'B') {
      if (b1 == -1) b1 = i;
      b2 = i;
    }
    if (a[i].op == 'R') {
      if (r1 == -1) r1 = i;
      r2 = i;
    }
  }
  return (a[b2].x-a[b1].x)+(a[r2].x-a[r1].x);
}

int main() {
  freopen("connect.in","r",stdin);
  freopen("connect.out","w",stdout);
  int n,pc = 0;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].x >> a[i].op;
    if (a[i].op == 'P') pid[++pc] = i;
  }
  int64_t ans = __30pts(1,pid[1]-1) + __30pts(pid[pc]+1,n);
  for (int i = 2; i <= pc; i++) {
    if (pid[i]-pid[i-1] == 1) { // 连续的两个P
      ans += a[pid[i]].x-a[pid[i-1]].x; // 加上区间走人
      continue;
    }
    int rc = 0, bc = 0;
    for (int j = pid[i-1]+1; j < pid[i]; j++) {
      if (a[j].op == 'R') rc++; 
      if (a[j].op == 'B') bc++;
    }
    if (rc == 0 || bc == 0) { // 如果两个P之间只有一种字母
      int64_t bggp = -1;
      for (int j = pid[i-1]+1; j <= pid[i]; j++) {
        bggp = max(bggp,a[j].x-a[j-1].x);
      }
      ans += 2*(a[pid[i]].x-a[pid[i-1]].x)-bggp; // 两个P连,剩下的城市串起来,断掉一条最长的
    } else {
      int64_t ans1 = 2*(a[pid[i]].x-a[pid[i-1]].x); // 两个国家自己用内部道路连自己的城市
      int64_t gpr = -1,gpb = -1;
      int lstr = pid[i-1], lstb = pid[i-1];
      for (int j = pid[i-1]+1; j <= pid[i]; j++) {
        if (a[j].op == 'R') {
          gpr = max(gpr,a[j].x-a[lstr].x);
          lstr = j;
        }
        if (a[j].op == 'B') {
          gpb = max(gpb,a[j].x-a[lstb].x);
          lstb = j;
        }
        if (a[j].op == 'P') {
          gpr = max(gpr,a[j].x-a[lstr].x);
          gpb = max(gpb,a[j].x-a[lstb].x);
          lstr = lstb = j;
        }
      }
      int64_t ans2 = 3*(a[pid[i]].x-a[pid[i-1]].x)-gpr-gpb; //两个P连,两个国家自己用内部道路连自己的城市,各自断掉一条最长的
      ans += min(ans1,ans2); // 取小的
    }
  }
  cout << ans;
  return 0;
}
// PBBPRRBPP
// (3+2)+(4+2+1)+1=13
2024/10/16 20:10
加载中...