题目

https://www.luogu.com.cn/problem/P2205

思路

刷水题真解压

差分就完事了

值得注意的一些东西:像这种和数轴或者坐标相关的题,还有扫描线题,一定要注意区间的开闭!!!

我个人的习惯是把坐标为\(x\)的点当成\([x,x+1)\)这段小区间来做,对于本题,因为求的是栅栏,用区间处理会更方便。

代码

点击查看代码
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#define maxn 200010
using namespace std;
int a[maxn],b[maxn],cnt=0,idx=0;
struct add{
int pos,val;
add(){}
add(int x,int y){pos=x,val=y;}
bool operator <(add t){
return pos<t.pos;
}
} delta[maxn];
int main(){
int i,j,n,m,k,x,p=0,ans=0;
char dir[3];
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i){
scanf("%d%s",&x,dir);
if(dir[0]=='L'){
delta[++cnt]=add(p,-1);
p-=x;
delta[++cnt]=add(p,1);
}
else{
delta[++cnt]=add(p,1);
p+=x;
delta[++cnt]=add(p,-1);
}
}
sort(delta+1,delta+cnt+1);
for(i=1;i<=cnt;++i){
if(i==1||delta[i].pos>delta[i-1].pos) b[++idx]=delta[i].pos;
a[idx]+=delta[i].val;
}
for(i=1;i<=idx;++i){
a[i]+=a[i-1];
if(a[i]>=k) ans+=b[i+1]-b[i];
}
printf("%d\n",ans);
// system("pause");
return 0;
}

最新文章

  1. 动手做第一个Chrome插件
  2. maven构建简单的web项目
  3. 如何在Mac OSX系统下安装Tomcat
  4. extJs学习基础3 ajax与php交互
  5. JDE开发端安装问题(JDE初步卸载重装)
  6. mysql西文字符大小写重复键问题的解决方法
  7. mMathf -》 Unity3d通用脚本
  8. hdu 4864 Task (贪心 技巧)
  9. margin的BUG(2)
  10. 在PHP中如何使用消息列队
  11. 转:基于IOS上MDM技术相关资料整理及汇总
  12. JavaScript重复元素处理
  13. 与众不同 windows phone (27) - Feature(特性)之搜索的可扩展性, 程序的生命周期和页面的生命周期, 页面导航, 系统状态栏
  14. 【CRC校验】学习笔记
  15. java2 - 语言基础
  16. android的Binder通信机制java层浅谈-android学习之旅(88)
  17. 统计一个数据库中,无记录的表的sql语句
  18. 部分手机(如三星)的Listview列表会自动加上黑线解决办法
  19. Fiddler抓包—搞定接口测试
  20. MySQL设置白名单教程

热门文章

  1. Spring学习笔记 - 第三章 - AOP与Spring事务
  2. 跟光磊学Java-macOS版Java8开发环境搭建(基于Intel x86 64-bit)
  3. 初学《python编程从入门到实践》web应用程序,出现错误
  4. 抽奖动画 - 播放svga动画
  5. 一、tcp三次握手
  6. angular---处于激活状态的路由加样式
  7. VUE基础之:visible.sync-模态框显示隐藏、elementUI dialog组件报错或者visible属性不生效问题
  8. OpenMP 线程同步 Construct 实现原理以及源码分析(上)
  9. Linux CentOS7查看软件包安装时间
  10. vue学习笔记(一) ---- vue指令(总体大纲)