BZOJ 4723 Flappy Bird

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

#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 ;
}
上一篇:谁用光了磁盘?Docker System命令详解


下一篇:Python设计模式 - UML - 类图(Class Diagram)