先按照绿点进行分块
第一个绿点和最后一个绿点之后很好处理不说了

两个绿点之间的讨论:
有两种方案
1:红(蓝)点和绿点顺序连接,距离为相邻绿点距离(也就是双倍绿点距离)
2:红(蓝)点和绿点的点阵中寻找最大的距离边,不连这一条,其他都顺序连,当然这样不连通,最后再绿点连接。(一个绿点距离+红(蓝)点阵处理 可以看到样例就是这样做的)

#include<iostream>
#include<map>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<set>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 3e5+5;
#define MS(x,y) memset(x,y,sizeof(x))
#define MP(x, y) make_pair(x, y) int dis[N]; int color[N]; vector<int> so;
int main() {
int n;
while(~scanf("%d", &n)) {
so.clear();
for(int i = 0; i < n; ++i) {
int a; char b[10];
scanf("%d %s", &a, b);
dis[i] = a;
color[i] = b[0]=='G'? 3 : (b[0]=='R'? 1:2);
} int ans = 0;
for(int i = 0; i < n; ++i) {
if(color[i] == 3) {
so.push_back(i);
}
} if(so.empty()) {
int st = -1, ed = 0;
for(int i = 0; i < n; ++i) {
if(color[i] == 1 && st == -1) st = i;
if(color[i] == 1) ed = i;
}
if(st != -1) ans += dis[ed] - dis[st]; st = -1; ed = 0;
for(int i = 0; i < n; ++i) {
if(color[i] == 2 && st == -1) st = i;
if(color[i] == 2) ed = i;
}
if(st != -1) ans += dis[ed] - dis[st]; printf("%d\n", ans);
continue;
} //1
for(int i = 0; i < so[0]; ++i) {
if(color[i] == 1) {
ans += dis[so[0]] - dis[i]; break;
}
}
for(int i = 0; i < so[0]; ++i) {
if(color[i] == 2) {
ans += dis[so[0]] - dis[i]; break;
}
} //2
for(int i = 0; i <= so.size()-2; ++i) {
int len = dis[so[i+1]] - dis[so[i]];
int tt = 0;
int maxx = 0; int pre = so[i];
for(int j = so[i] + 1; j <= so[i+1]; ++j) {
if(color[j] != 1 ) {
// printf("%d\n", j);
maxx = max(maxx, dis[j] - dis[pre]);
pre = j;
}
}
tt += dis[so[i + 1]] - dis[so[i]] - maxx; maxx = 0; pre = so[i];
for(int j = so[i] + 1; j <= so[i+1]; ++j) {
if(color[j] != 2) {
maxx = max(maxx, dis[j] - dis[pre]);
pre = j;
}
}
tt += dis[so[i + 1]] - dis[so[i]] - maxx; if(tt > len) tt = len;
tt += len;
ans += tt; } //3
for(int i = n-1; i > so[so.size()-1]; --i) {
if(color[i] == 1) {
ans += dis[i] - dis[so[so.size()-1]]; break;
}
}
for(int i = n-1; i > so[so.size()-1]; --i) {
if(color[i] == 2) {
ans += dis[i] - dis[so[so.size()-1]]; break;
}
} printf("%d\n", ans);
}
return 0;
}

最新文章

  1. SDWebImage原理及使用(转)
  2. 【转】iOS学习之Storyboard中的UIScrollView使用自动布局
  3. WP8 MediaElement 实现循环播放
  4. Base64简介
  5. Erlang垃圾回收机制的二三事
  6. Mysql存储过程查询结果赋值到变量的方法
  7. node.js整理 05进程管理
  8. Html_在线客服静态网页
  9. 【BOZJ 1901】Zju2112 Dynamic Rankings
  10. Bootstrap 内核引用(一)
  11. php Ajax 局部刷新
  12. 二分法-C++
  13. git add -f
  14. Phonegap环境配置
  15. mongodb 在windows下面进行副本建创建
  16. H5中用postMessage传递数据,解决localStorage不能跨域问题
  17. iframe实用操作
  18. k8s全栈监控之metrics-server和prometheus
  19. 网页title左边显示网页的logo图标
  20. linux中service的问题

热门文章

  1. CF 375D. Tree and Queries加强版!!!【dfs序分块 大小分类讨论】
  2. django-rest-framework之请求与响应
  3. new day
  4. PLECS—晶闸管-第九周
  5. IOS设备设计完整指南
  6. Math.abs(~2018),掌握规律!
  7. sql server两个时间段内,求出周末的量
  8. 解析JavaScript函数的多种写法
  9. Python自动化--语言基础6--模块操作之re、MySQL、Excel
  10. SmileyFace——基于OpenCV的人脸人眼检测、面部识别程序