洛谷P2205 [USACO13JAN]Painting the Fence S
2024-10-21 09:37:56
题目
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;
}
最新文章
- 动手做第一个Chrome插件
- maven构建简单的web项目
- 如何在Mac OSX系统下安装Tomcat
- extJs学习基础3 ajax与php交互
- JDE开发端安装问题(JDE初步卸载重装)
- mysql西文字符大小写重复键问题的解决方法
- mMathf -》 Unity3d通用脚本
- hdu 4864 Task (贪心 技巧)
- margin的BUG(2)
- 在PHP中如何使用消息列队
- 转:基于IOS上MDM技术相关资料整理及汇总
- JavaScript重复元素处理
- 与众不同 windows phone (27) - Feature(特性)之搜索的可扩展性, 程序的生命周期和页面的生命周期, 页面导航, 系统状态栏
- 【CRC校验】学习笔记
- java2 - 语言基础
- android的Binder通信机制java层浅谈-android学习之旅(88)
- 统计一个数据库中,无记录的表的sql语句
- 部分手机(如三星)的Listview列表会自动加上黑线解决办法
- Fiddler抓包—搞定接口测试
- MySQL设置白名单教程
热门文章
- Spring学习笔记 - 第三章 - AOP与Spring事务
- 跟光磊学Java-macOS版Java8开发环境搭建(基于Intel x86 64-bit)
- 初学《python编程从入门到实践》web应用程序,出现错误
- 抽奖动画 - 播放svga动画
- 一、tcp三次握手
- angular---处于激活状态的路由加样式
- VUE基础之:visible.sync-模态框显示隐藏、elementUI dialog组件报错或者visible属性不生效问题
- OpenMP 线程同步 Construct 实现原理以及源码分析(上)
- Linux CentOS7查看软件包安装时间
- vue学习笔记(一) ---- vue指令(总体大纲)