題目描述

《飛揚的小鳥》是一款風靡的小游戲。在游戲中，小鳥一開始位于(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<=X<=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]。

輸出

如果無論如何都飛不到目的地，輸出NIE，否則輸出點擊屏幕的最少次數。

樣例輸入

4 11
4 1 4
7 -1 2
8 -1 3
9 0 2

樣例輸出

5

提示

?

因為只要通過最后一個障礙就能通關，所以只要維護通過每個障礙時最高及最低能飛到的高度范圍，判斷范圍是否為空集就好了。

相鄰兩個障礙間的距離就是小鳥最高能往上飛多少或最低能往下降多少。

因為每走一步要么是x+1,y-1；要么是x+1,y+1。所以橫縱坐標和一定是偶數，將過最后一個障礙后(最低縱坐標+橫坐標)/2就是最少需要點擊屏幕數。

#include<set> #include<map> #include<queue> #include<stack> #include<cmath> #include<vector> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define ll long long using namespace std; int x[500010]; int a[500010]; int b[500010]; int A,B; int n; int main() {scanf("%d%*d",&n);for(int i=1;i<=n;i++){scanf("%d%d%d",&x[i],&a[i],&b[i]);}for(int i=1;i<=n;i++){int sum=x[i]-x[i-1];A=max(A-sum,a[i]+1);B=min(B+sum,b[i]-1);if((A&1)!=(x[i]&1)){A++;}if((B&1)!=(x[i]&1)){B--;}if(A>B){printf("NIE");return 0;}}printf("%d",(A+x[n])/2); }

轉載于:https://www.cnblogs.com/Khada-Jhin/p/9637257.html

總結

以上是生活随笔為你收集整理的BZOJ4723[POI2017]Flappy Bird——模拟的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。