找到可行区间,最优解一定在区间的下端点。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define maxn 500500
using namespace std;
int n,X,x[maxn],a[maxn],b[maxn],l[maxn],r[maxn],ans=;
int read()
{
char ch;int data=,f=;
while (ch<'' || ch>'') {if (ch=='-') f=-;ch=getchar();}
while (ch>='' && ch<='')
{
data=data*+ch-'';
ch=getchar();
}
return data*f;
}
int main()
{
n=read();X=read();
for (int i=;i<=n;i++)
x[i]=read(),a[i]=read(),b[i]=read();
l[]=r[]=;
for (int i=;i<=n;i++)
{
l[i]=max(l[i-]-(x[i]-x[i-]),a[i]+);
r[i]=min(r[i-]+(x[i]-x[i-]),b[i]-);
if (l[i]>r[i]) {printf("NIE\n");return ;}
}
int ret=;
for (int i=;i<=n;i++)
{
if (x[i]>X) break;
int now=x[i]-x[i-]+l[i]-ret;
if (now%) {l[i]++;now++;}
if (l[i]>r[i]) {printf("NIE\n");return ;}
if (now>) ans+=now/;ret=l[i];
}
printf("%d\n",ans);
return ;
}

最新文章

  1. VMware中CPU分配不合理以及License限制引起的SQL Scheduler不能用于查询处理
  2. PHP变量在内存中的存储方式
  3. 发测试 HTML/FILE/MYSQL/动态 20151120
  4. java.net.URLConnectioin的http(get,post)请求(原生)
  5. 常用的adb命令
  6. thinkPHP 接支付宝及时到账接口
  7. 关于spring 事物传播性的研究
  8. xcode 产生指定颜色的图片imageWithColor
  9. 【推理】UVa 10771 - Barbarian tribes
  10. nodejs实现单文件上传。
  11. PHP经验——获得PHP版本信息及版本比较
  12. MVC - 云服务器部署
  13. Discuz论坛提速优化技巧
  14. 【视频编解码&#183;学习笔记】2. H.264简介
  15. 学习笔记_J2EE_Spring(一)_入门
  16. 阿里云ECS装LAMP环境
  17. 【Python】数据库练习-1
  18. 素数回文(hdu1431)
  19. Hibernate中Session.get()方法和load()方法的详细比较
  20. Flume与Logstash比较

热门文章

  1. 在Windows8.1中通过IIS发布网站产生HTTP Error 503错误的解决方案
  2. (31)odoo中的时间
  3. MyBatis框架Maven资源
  4. Linux下把Mysql和Apache加入到系统服务里
  5. SecureCRT从本传相片到服务器的注意事项
  6. group_concat函数与find_in_set()函数相结合
  7. MYSQL 日期函数【转】
  8. Octopus系列之HttpCustom2.0模板引擎的处理,一个bug的分析
  9. Kafka简要图解
  10. [Js]封装好的通过className来获取元素的函数