题解：P5957 [POI 2017] Flappy Bird

· · 题解

P5957 [POI 2017] Flappy Bird 题解。

传送门

我们注意到，不点击时，纵坐标减少 1，横坐标增加 1，和不变，点击时，纵横坐标各增加 1 一共增加 2。

所以求点 (x,y) 的点击次数就是 \frac{x+y}{2} 次。

我们需要维护一个区间 [l,r] 来表示能通过当前障碍物的点击次数的取值。考虑只计算通过每个障碍物的点击次数的上下界，随后不断取最大最小值维护即可。

这样不合法情况就是 l>r 了，输出并结束程序即可。

时间复杂度为 O(n) 是完全可以通过的。

代码如下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,xx;
ll l,r,la,x,a,b;
ll dis,lo,hi;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>xx;
    for(int i=1;i<=n;i++){
        cin>>x>>a>>b;
        dis=x-la;
        //计算当前位移
        r+=dis;
        //lo hi 表示只计算通过当前障碍物的点击次数的上下界
        lo=(a+x+1+1)/2,hi=(b+x-1)/2;
        //更新l,r
        l=max(l,lo);
        r=min(r,hi);
        //不符合
        if(l>r){
            cout<<"NIE\n";
            return 0;
        }
        la=x;
    }
    dis=xx-la;
    r+=dis;
    cout<<l;
    return 0;
}

谢谢观看。