【BZOJ3387】[Usaco2004 Dec]Fence Obstacle Course柵欄行動(dòng)

Description

約翰建造了N(1≤N≤50000)個(gè)柵欄來與牛同樂．第i個(gè)柵欄的z坐標(biāo)為[Ai.，Bi]（-100000≤Ai<Bi≤10^5），y坐標(biāo)為i．牛棚的外欄即x軸，原點(diǎn)是牛棚的門．奶牛們開始處于(S，N)，她們需要回到牛棚的門（下圖中用“*’表示）． 約翰的初衷是為了給奶牛們練習(xí)跳躍，但是奶牛們似乎更愿意四蹄著地，慢慢她沿著柵欄 走．當(dāng)她們走到柵欄的盡頭，就會(huì)朝著牛棚的個(gè)欄方向（即y軸負(fù)方向）行走，直到碰上另一條柵欄或是牛棚外欄．這時(shí)候她們便要選擇繼續(xù)向左走，還是向右走．奶牛們希望走的路程最短．由于可方向的路程一定，你只需求出z方向走的最短路程，使奶牛回到原點(diǎn)．

Input

第1行：N，S(-100000≤S≤100000)． 第2到N+1行：每行2個(gè)整數(shù)Ai，Bi，(-100000≤Ai≤Bi≤100000)．

Output

最小的x方向的步數(shù)

Sample Input

4 0
-2 1
-1 2
-3 0
-2 1

Sample Output

4

HINT

?

題解：本題做法有很多。我是先列了個(gè)樸素的方程，設(shè)f[i][0/1]表示走到第i個(gè)柵欄左/右邊界的最小路程，轉(zhuǎn)移如下

然后就根據(jù)絕對(duì)值分兩種情況討論，每個(gè)都建一個(gè)線段樹維護(hù)一下就好了

注意此題從（S，N）開始！

?

#include <cstdio> #include <iostream> #include <cstring> #define lson x<<1 #define rson x<<1|1 using namespace std; const int maxn=200005; int n,m; int s[maxn<<2][2],t[maxn<<2][2]; void pushdown(int x,int p) {if(t[x][p]){s[lson][p]=s[rson][p]=1<<30;t[lson][p]=t[rson][p]=1;t[x][p]=0;} } void updata(int l,int r,int x,int a,int b,int p) {if(l==r){s[x][p]=min(s[x][p],b);return ;}pushdown(x,p);int mid=l+r>>1;if(a<=mid) updata(l,mid,lson,a,b,p);else updata(mid+1,r,rson,a,b,p);s[x][p]=min(s[lson][p],s[rson][p]); } void cover(int l,int r,int x,int a,int b,int p) {if(a<=l&&r<=b){t[x][p]=1,s[x][p]=1<<30;return ;}pushdown(x,p);int mid=l+r>>1;if(a<=mid) cover(l,mid,lson,a,b,p);if(b>mid) cover(mid+1,r,rson,a,b,p);s[x][p]=min(s[lson][p],s[rson][p]); } int query(int l,int r,int x,int a,int b,int p) {if(a<=l&&r<=b) return s[x][p];pushdown(x,p);int mid=l+r>>1;if(b<=mid) return query(l,mid,lson,a,b,p);if(a>mid) return query(mid+1,r,rson,a,b,p);return min(query(l,mid,lson,a,b,p),query(mid+1,r,rson,a,b,p)); } int main() {scanf("%d%d",&n,&m);m+=100002;memset(s,0x3f,sizeof(s));updata(1,maxn,1,100002,-100002,0),updata(1,maxn,1,100002,100002,1);int i,a,b,ta,tb;for(i=1;i<=n;i++){scanf("%d%d",&a,&b);a+=100002,b+=100002;ta=min(query(1,maxn,1,1,a,0)+a,query(1,maxn,1,a+1,maxn,1)-a);tb=min(query(1,maxn,1,1,b,0)+b,query(1,maxn,1,b+1,maxn,1)-b);updata(1,maxn,1,a,ta-a,0),updata(1,maxn,1,a,ta+a,1);updata(1,maxn,1,b,tb-b,0),updata(1,maxn,1,b,tb+b,1);if(b>a+1) cover(1,maxn,1,a+1,b-1,0),cover(1,maxn,1,a+1,b-1,1);}printf("%d",min(query(1,maxn,1,1,m,0)+m,query(1,maxn,1,m+1,maxn,1)-m));return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/CQzhangyu/p/6421252.html

總結(jié)

以上是生活随笔為你收集整理的【BZOJ3387】[Usaco2004 Dec]Fence Obstacle Course栅栏行动 线段树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。