【CF962E】Byteland, Berland and Disputed Cities
2024-08-26 01:47:30
几句话题意
数轴上面有三种点(B点,R点,P点),现在要将其中的某些点连起来,满足将所有B点去掉之后,所有P点和R点都连通&将所有R点去掉之后,所有B点和P点都连通两个条件,连接两点的代价为数轴上距离,求最小代价(读入按照数轴上位置从小到大的顺序)
Solution
这题。。其实是个特别神秘的贪心
首先有个特别直接的想法,就是。。所有的B点和它的前一个B点或者P点连,所有的R点和它的前一个R点或者P点连,P点和前一个R点和前一个B点连,这样就一定能保证满足那两个条件并且不会绕多太多路
但是,画一下图会发现,其实还有一种连法是将一个P点和它的前一个P点连起来,这样这两个P点之间就可以省掉两条边(B与B连的一条,R与R连的一条)弱弱的我一开始完全没想到这个Q^Q
那么最优解应该就是在这两种情况中取较小的那个就好了
具体实现的话,因为保证读入是按顺序的,那就一开始先全部按照第一种方法连,如果当前有两个P点那么就与第二种连法取最优解就好了,中间稍微记录一下边的最大值即可
代码大概长这个样子
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=2*(1e5)+10,inf=2147483647;
ll ans;
int n,lastR,lastB,lastP,mxR,mxB;
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
#endif
int x;
char c;
scanf("%d",&n);
lastR=lastB=lastP=-inf;
mxR=mxB=0;
for (int i=1;i<=n;++i){
scanf("%d %c\n",&x,&c);
if (c=='R'||c=='P'){
if (lastR!=-inf)
ans+=x-lastR,mxR=max(mxR,x-lastR);
lastR=x;
}
if (c=='B'||c=='P'){
if (lastB!=-inf)
ans+=x-lastB,mxB=max(mxB,x-lastB);
lastB=x;
}
if (c=='P'){
if (lastP!=-inf)
ans+=min(0,x-lastP-mxR-mxB);
lastP=x; mxR=mxB=0;
}
}
printf("%I64d\n",ans);
}
最新文章
- Easymake
- DSP下的#program
- android中ColorStateList及StateListDrawable设置Selector
- 基于OSGI.Net的图形界面系统
- Dalvik字节码的类型,方法与字段表示方法
- Oracle_Q&;A_02
- Typecho 代码阅读笔记(一) - 页面渲染及路由机制
- python命令行参数处理
- gradle入门(1-5)创建并运行Web应用
- Spring Cloud微服务实践之路-起始
- 纯css实现checkbox开关切换按钮
- 网络-01-端口号-linux端口详解大全
- Spring Cloud Config 分布式配置中心【Finchley 版】
- FastAdmin 基本知识流程一栏
- Egret中使用P2物理引擎
- MonkeyRunner 之如何获取APP的Package Name和Activity Name
- vue中动态绑定class
- webpack的使用一
- plsql 连接oracle数据库的2种方式
- JS中onclick事件传参
热门文章
- 《物质世界 (Outward)》证明不必压缩制作大型角色扮演游戏的时间
- 002 -- MySQL的逻辑架构
- 在进行分布式框架搭建的过程中,出现问题advised by org.springframework.transaction.interceptor.TransactionInterceptor.invoke(org.aopalliance.intercept.MethodInvocation)?
- python程序设计——面向对象程序设计:继承
- Laxcus大数据操作系统单机集群版
- day06 再谈编码 and 作业讲解
- c# ms chart 控件使用方法
- /proc/sys目录下各文件参数说明
- Codeforces Round #613 Div.1 D.Kingdom and its Cities 贪心+虚树
- 7. I/O复用