| ||||||||||
| 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