正文
BZOJ 4723: [POI2017]Flappy Bird
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
Description
从一个点到一条直线,每次纵坐标只能增加或减少1,有些位置有障碍,求最少增加步数.
Sol
贪心.
或许是贪心吧...反正在可到达的范围内,纵坐标尽量小...
做的时候维护一下两个端点,因为在这个区间内操作数单调递增,只需要取最下面的点就好.
Code/**************************************************************
Problem: 4723
User: BeiYu
Language: C++
Result: Accepted
Time:1884 ms
Memory:1284 kb
****************************************************************/#include <cstdio>
#include <iostream>
using namespace std;#define debug(a) cout<<#a<<"="<<a<<" "int n,m,ans;
int X,L,R;int main(){
// freopen("in.in","r",stdin);
ios::sync_with_stdio(false); cin>>n>>m; X=L=R=0; for(int i=1;i<=n;i++){
int x,l,r,t;
cin>>x>>l>>r;
l++,r--; t=(x-X); l=max(l,L-t);
r=min(r,R+t); if((l-L+t)&1) l++;
if((r-R+t)&1) r--; if(L<l-t) ans+=(l-t-L)>>1,L=l-t;
if(R>r+t) R=r+t; if(L>R) return puts("NIE"),0; ans+=(l-L+t)>>1;// cout<<"-----------------"<<i<<"-------------------"<<endl;
// debug(X),debug(L),debug(R)<<endl;
// debug(x),debug(l),debug(r)<<endl;
// debug(t),debug(((l-L+t)>>1))<<endl; L=l;
R=r;
X=x; if(L>R) return puts("NIE"),0;
}
cout<<ans<<endl;
return 0;
}
/**************************************************************
Problem: 4723
User: BeiYu
Language: C++
Result: Accepted
Time:1884 ms
Memory:1284 kb
****************************************************************/#include <cstdio>
#include <iostream>
using namespace std;#define debug(a) cout<<#a<<"="<<a<<" "int n,m,ans;
int X,L,R;int main(){
// freopen("in.in","r",stdin);
ios::sync_with_stdio(false); cin>>n>>m; X=L=R=0; for(int i=1;i<=n;i++){
int x,l,r,t;
cin>>x>>l>>r;
l++,r--; t=(x-X); l=max(l,L-t);
r=min(r,R+t); if((l-L+t)&1) l++;
if((r-R+t)&1) r--; if(L<l-t) ans+=(l-t-L)>>1,L=l-t;
if(R>r+t) R=r+t; if(L>R) return puts("NIE"),0; ans+=(l-L+t)>>1;// cout<<"-----------------"<<i<<"-------------------"<<endl;
// debug(X),debug(L),debug(R)<<endl;
// debug(x),debug(l),debug(r)<<endl;
// debug(t),debug(((l-L+t)>>1))<<endl; L=l;
R=r;
X=x; if(L>R) return puts("NIE"),0;
}
cout<<ans<<endl;
return 0;
}
