问题 A: Flappy Bird
时间限制: 1 Sec 内存限制: 128 MB提交: 404 解决: 72
[提交] [状态] [讨论版] [命题人:admin]
题目描述
《飞扬的小鸟》是一款风靡的小游戏。在游戏中,小鸟一开始位于(0,0)处,它的目标是飞到横坐标为X的某个位置上。每一秒,你可以选择点击屏幕,那么小鸟会从(x,y)飞到(x+1,y+1),或者不点击,那么小鸟会飞到(x+1,y-1)。在游戏中还有n个障碍物,用三元组(x[i],a[i],b[i])描述,表示在直线x=x[i]上,y<=a[i]或者y>=b[i]的部分都是障碍物,碰到或者擦边都算游戏失败。请求出小鸟从(0,0)飞到目的地最少需要点击多少次屏幕。
输入
第一行包含两个整数n(0<=n<=500000),X(1<=n<=10^9)。
接下来n行,每行三个整数x[i],a[i],b[i](0<x[i]<X,-10^9<=a[i]<b[i]<=10^9)。
数据保证x[i]<x[i+1]。
接下来n行,每行三个整数x[i],a[i],b[i](0<x[i]<X,-10^9<=a[i]<b[i]<=10^9)。
数据保证x[i]<x[i+1]。
输出
如果无论如何都飞不到目的地,输出NIE,否则输出点击屏幕的最少次数。
样例输入
4 11
4 1 4
7 -1 2
8 -1 3
9 0 2
样例输出
5
提示
题意
中文题意,不做解释。
分析
1、这个鸟要从(0,0)到(x,y)不管怎么飞必须要点击(x+y)/2次
2、对于同一列的障碍物,鸟可以计算出来一个能飞到的最高点和最低点。
3、一直递推到最后,利用1推出的结论求出点击次数即可。
/// author:Kissheart /// #include<stdio.h> #include<algorithm> #include<iostream> #include<string.h> #include<vector> #include<stdlib.h> #include<math.h> #include<queue> #include<deque> #include<ctype.h> #include<map> #include<set> #include<stack> #include<string> #define INF 0x3f3f3f3f #define FAST_IO ios::sync_with_stdio(false) const double PI = acos(-1.0); const double eps = 1e-6; const int MAX=5e5+10; const int mod=1e9+7; typedef long long ll; using namespace std; #define gcd(a,b) __gcd(a,b) inline ll lcm(ll a,ll b){return a/gcd(a,b)*b;} inline ll qpow(ll a,ll b){ll r=1,t=a; while(b){if(b&1)r=(r*t)%mod;b>>=1;t=(t*t)%mod;}return r;} inline ll inv1(ll b){return qpow(b,mod-2);} inline ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll r=exgcd(b,a%b,y,x);y-=(a/b)*x;return r;} inline ll read(){ll x=0,f=1;char c=getchar();for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;for(;isdigit(c);c=getchar()) x=x*10+c-'0';return x*f;} //freopen( "in.txt" , "r" , stdin ); //freopen( "data.txt" , "w" , stdout ); ll n,X; ll x[MAX],a[MAX],b[MAX]; int main() { scanf("%lld%lld",&n,&X); for(ll i=1;i<=n;i++) scanf("%lld%lld%lld",&x[i],&a[i],&b[i]); ll t,maxn=0,minn=0,last=0,p; for(ll i=1;i<=n;i++) { t=x[i]-last; maxn=maxn+t; minn=minn-t; if(minn<=a[i]) { p=a[i]-minn; if(p%2) p+=1; else p+=2; minn=minn+p; } if(maxn>=b[i]) { p=maxn-b[i]; if(p%2) p+=1; else p+=2; maxn=maxn-p; } //printf("%lld %lld ",minn,maxn); if(maxn<minn) { printf("NIE "); return 0; } last=x[i]; } printf("%lld ",(minn+x[n])/2); return 0; }