Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
不需要线段树,类似DP的思想,加一个队列表示层次。#include <stdio.h> #include <string> #include <string.h> #include <queue> #include <stack> #include <map> #include <iostream> #include <stdlib.h> #include <math.h> #include <algorithm> #define mod 10e9+7; #define inf 0x3f3f3f3f #define mem0(x , y) memset(x , y , sizeof(x)) using namespace std; const int MAX = 55000 ; const int MAXL = 100505 ; int data[MAX][2] ; int dp[MAXL*2] ; int vis[MAXL*2] ; int main(){ ///freopen("input" , "r" ,stdin) ; int n , s ; int a , b ; scanf("%d%d",&n,&s) ; s += MAXL ; for(int i=1;i<=n;i++){ scanf("%d%d",&a,&b) ; data[i][0] = a + MAXL ; data[i][1] = b + MAXL; } mem0(dp , inf) ; queue <int> que ; que.push(s) ; dp[s] = 0 ;vis[s] = 1 ; for(int i=n;i>=1;i--){ int k = que.size() ; while(k --){ int now = que.front() ; que.pop() ; vis[now] = 0 ; if(now <= data[i][0] || now >= data[i][1]) { if(!vis[now]){ que.push(now) ; vis[now] = 1; } } else { dp[data[i][0]] = min(dp[data[i][0]] , dp[now] + abs(now-data[i][0])) ; dp[data[i][1]] = min(dp[data[i][1]] , dp[now] + abs(now-data[i][1])) ; dp[now] = inf ; if(!vis[data[i][0]]) { que.push(data[i][0]) ; vis[data[i][0]] = 1 ; } if(!vis[data[i][1]]){ que.push(data[i][1]) ; vis[data[i][1]] = 1 ; } } } } int ans = inf ; while(!que.empty()){ int now = que.front() ; que.pop() ; ans = min(dp[now] + abs(now-MAXL) , ans ) ; } printf("%d\n",ans ) ; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator