http://www.elijahqi.win/archives/959

【問題描述】

小 A 和小 B 決定利用假期外出旅行，他們将想去的城市從 1 到 N 編号，且編号較小的城市在編号較大的城市的西邊，已知各個城市的海拔高度互不相同，記城市 i 的海拔高度為 Hi，城市 i 和城市 j 之間的距離 d[i,j]恰好是這兩個城市海拔高度之差的絕對值，即

d[i, j] = |?? − ??|。

旅行過程中，小 A 和小 B 輪流開車，第一天小 A 開車，之後每天輪換一次。他們計劃選擇一個城市 S 作為起點，一直向東行駛，并且最多行駛 X 公裡就結束旅行。小 A 和小 B 的駕駛風格不同，小 B 總是沿着前進方向選擇一個最近的城市作為目的地，而小 A 總是沿着前進方向選擇第二近的城市作為目的地（注意：本題中如果目前城市到兩個城市的距離相同，則認為離海拔低的那個城市更近）。如果其中任何一人無法按照自己的原則選擇目的城市，或者到達目的地會使行駛的總距離超出 X 公裡，他們就會結束旅行。

在啟程之前，小 A 想知道兩個問題：

1．對于一個給定的 X=X0，從哪一個城市出發，小 A 開車行駛的路程總數與小 B 行駛的路程總數的比值最小（如果小 B 的行駛路程為 0，此時的比值可視為無窮大，且兩個無窮大視為相等）。如果從多個城市出發，小 A 開車行駛的路程總數與小 B 行駛的路程總數的比值都最小，則輸出海拔最高的那個城市。

對任意給定的 X=Xi 和出發城市 Si，小 A 開車行駛的路程總數以及小 B 行駛的路程總數。

【輸入】

輸入檔案為 drive.in。

第一行包含一個整數 N，表示城市的數目。

第二行有 N 個整數，每兩個整數之間用一個空格隔開，依次表示城市 1 到城市 N 的海拔高度，即 H1，H2，……，Hn，且每個 Hi 都是不同的。

第三行包含一個整數 X0。

第四行為一個整數 M，表示給定 M 組 Si 和 Xi。

接下來的 M 行，每行包含 2 個整數 Si 和 Xi，表示從城市 Si 出發，最多行駛 Xi 公裡。

【輸出】

輸出檔案為 drive.out。

輸出共 M+1 行。

第一行包含一個整數 S0，表示對于給定的 X0，從編号為 S0 的城市出發，小 A 開車行駛的路程總數與小 B 行駛的路程總數的比值最小。

接下來的 M 行，每行包含 2 個整數，之間用一個空格隔開，依次表示在給定的 Si 和

Xi 下小 A 行駛的裡程總數和小 B 行駛的裡程總數。

【輸入輸出樣例 1】

drive.in drive.out

2 3 1 4

1 3

2 3

3 3

4 3

1 1

2 0

0 0

【輸入輸出樣例 1 說明】

各個城市的海拔高度以及兩個城市間的距離如上圖所示。

如果從城市 1 出發，可以到達的城市為 2,3,4，這幾個城市與城市 1 的距離分别為 1,1,2，但是由于城市 3 的海拔高度低于城市 2，是以我們認為城市 3 離城市 1 最近，城市 2 離城市 1 第二近，是以小 A 會走到城市 2。到達城市 2 後，前面可以到達的城市為 3,4，這兩個城市與城市 2 的距離分别為 2,1，是以城市 4 離城市 2 最近，是以小 B 會走到城市 4。到達城市 4 後，前面已沒有可到達的城市，是以旅行結束。

如果從城市 2 出發，可以到達的城市為 3,4，這兩個城市與城市 2 的距離分别為 2,1，由于城市 3 離城市 2 第二近，是以小 A 會走到城市 3。到達城市 3 後，前面尚未旅行的城市為 4，是以城市 4 離城市 3 最近，但是如果要到達城市 4，則總路程為 2+3=5>3，是以小 B 會直接在城市 3 結束旅行。

如果從城市 3 出發，可以到達的城市為 4，由于沒有離城市 3 第二近的城市，是以旅行還未開始就結束了。

如果從城市 4 出發，沒有可以到達的城市，是以旅行還未開始就結束了。

【輸入輸出樣例 2】

drive.in drive.out

4 5 6 1 2 3 7 8 9 10

1 7

2 7

3 7

4 7

5 7

6 7

7 7

8 7

9 7

10 7

3 2

2 4

2 1

2 4

5 1

2 1

2 0

0 0

【輸入輸出樣例 2 說明】當 X=7 時，

如果從城市 1 出發，則路線為 1 -> 2 -> 3 -> 8 -> 9，小 A 走的距離為 1+2=3，小 B 走的距離為 1+1=2。（在城市 1 時，距離小 A 最近的城市是 2 和 6，但是城市 2 的海拔更高，視為與城市 1 第二近的城市，是以小 A 最終選擇城市 2；走到 9 後，小 A 隻有城市 10 可以走，沒有第 2 選擇可以選，是以沒法做出選擇，結束旅行）

如果從城市 2 出發，則路線為 2 -> 6 -> 7 ，小 A 和小 B 走的距離分别為 2，4。如果從城市 3 出發，則路線為 3 -> 8 -> 9，小 A 和小 B 走的距離分别為 2，1。如果從城市 4 出發，則路線為 4 -> 6 -> 7，小 A 和小 B 走的距離分别為 2，4。

如果從城市 5 出發，則路線為 5 -> 7 -> 8 ，小 A 和小 B 走的距離分别為 5，1。如果從城市 6 出發，則路線為 6 -> 8 -> 9，小 A 和小 B 走的距離分别為 5，1。

如果從城市 7 出發，則路線為 7 -> 9 -> 10，小 A 和小 B 走的距離分别為 2，1。

如果從城市 8 出發，則路線為 8 -> 10，小 A 和小 B 走的距離分别為 2，0。

如果從城市 9 出發，則路線為 9，小 A 和小 B 走的距離分别為 0，0（旅行一開始就結束了）。

如果從城市 10 出發，則路線為 10，小 A 和小 B 走的距離分别為 0，0。從城市 2 或者城市 4 出發小 A 行駛的路程總數與小 B 行駛的路程總數的比值都最小，

但是城市 2 的海拔更高，是以輸出第一行為 2。

【資料範圍】對于 30%的資料，有 1≤N≤20，1≤M≤20；對于 40%的資料，有 1≤N≤100，1≤M≤100；對于 50%的資料，有 1≤N≤100，1≤M≤1,000；

對于 70%的資料，有 1≤N≤1,000，1≤M≤10,000；

對于 100%的資料，有 1≤N≤100,000，1≤M≤10,000，-1,000,000,000≤Hi≤1,000,000,000， 0≤X0≤1,000,000,000，1≤Si≤N，0≤Xi≤1,000,000,000，資料保證 Hi 互不相同。

這題我真是很多句mmp要講耗了我很久

直接預處理加模拟可以拿到70分的成績

mmp 模拟賽我竟然沒寫tmd

include

define inf 0x7fffffff

define N 1100

inline int read(){

int x=0,f=1;char ch=getchar();

while (ch<’0’||ch>’9’){if (ch==’-‘)f=-1;ch=getchar();}

while (ch<=’9’&&ch>=’0’){x=x*10+ch-‘0’;ch=getchar();}

return x*f;

}

inline int max(int x,int y){return x>y?x:y;}

struct node{

int len,y,height;

node(){

len=inf;

}

}dis[N],dis1[N];

inline int abs(int a){

if (a<0) return -a;else return a;

}

int a2,b2,h[N],x0,n;

void work(int x){

int op=1;//op=1 小a開車op=0 b開車

int len=0;

while (1){

if(op==0){

if (len+dis[x].len>x0) break;

if (dis[x].y==0) break;

len+=dis[x].len;

b2+=dis[x].len;

x=dis[x].y;

} else{

if (len+dis1[x].len>x0)break;

if (dis1[x].y==0) break;

len+=dis1[x].len;

a2+=dis1[x].len;

x=dis1[x].y;

}

op^=1;

}

int main(){

//freopen(“drive.in”,”r”,stdin);

// freopen(“drive.out”,”w”,stdout);

n=read();

for (int i=1;i<=n;++i) h[i]=read();int max1=inf,max2=inf;

for (int i=1;i<=n;++i){

for (int j=i+1;j<=n;++j){

if (i==j) continue;

if (abs(h[i]-h[j])

#include<cstdio>
#include<algorithm>
#include<map>
#include<set>
#define N 110000
#define inf 0x7f7f7f7f
using namespace std;
inline int read(){
    int x=,f=;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-;ch=getchar();}
    while (ch<='9'&&ch>='0'){x=x*+ch-'0';ch=getchar();}
    return x*f;
}
set<int> q;map<int,int> mm;
struct node1{
    int height,key;
}t[];
inline bool cmp(node1 a,node1 b){
    if (a.key==b.key) return a.height<b.height;return a.key<b.key;
}
int to[N][],valuea[N][],valueb[N][],n,h[N],fa[N],fb[N],a[N],b[N],a2,b2;
inline double work(int x,int x0){
    for (int j=;j>=;--j){
        if (to[x][j]&&valuea[x][j]+valueb[x][j]<=x0){
            a2+=valuea[x][j];b2+=valueb[x][j];
            x0-=valuea[x][j]+valueb[x][j];x=to[x][j];
        }
    }
    if (b2==) return inf;
    return (double) a2/(double) b2;
}
inline void work1(int x,int x0){
    for (int j=;j>=;--j){
        if (to[x][j]&&valuea[x][j]+valueb[x][j]<=x0){
            a2+=valuea[x][j];b2+=valueb[x][j];
            x0-=valuea[x][j]+valueb[x][j];x=to[x][j];
        }
    }
}
int main(){
    freopen("drive.in","r",stdin);
    n=read();
    for (int i=;i<=n;++i) h[i]=read(),mm[h[i]]=i;q.insert(inf);q.insert(-inf);
    for (int i=n;i>=;--i){
        q.insert(h[i]);
        t[].height=*--q.lower_bound(h[i]);t[].height=*q.upper_bound(h[i]);
        if (t[].height!=-inf) t[].height=*--q.lower_bound(t[].height);else t[].height=-inf;
        if (t[].height!=inf) t[].height=*q.upper_bound(t[].height);else t[].height=inf;
        for (int j=;j<=;++j) t[j].key=abs(t[j].height-h[i]);
        sort(t+,t+,cmp);
        a[i]=t[].key;b[i]=t[].key;
        fa[i]=mm[t[].height];fb[i]=mm[t[].height];
    //  printf("%d %d\n",a[i],fa[i]);printf("%d %d\n",b[i],fb[i]);
        for (int j=;j<=;++j){
            if (j==){
                if (fa[i]) to[i][]=fa[i],valuea[i][]=a[i];
            }else if (j==){
                if (fb[fa[i]])
                to[i][]=fb[fa[i]],valuea[i][]=a[i],valueb[i][]=b[fa[i]];
            }else if(to[to[i][j-]][j-]) {
                to[i][j]=to[to[i][j-]][j-];
                valuea[i][j]=valuea[i][j-]+valuea[to[i][j-]][j-];
                valueb[i][j]=valueb[i][j-]+valueb[to[i][j-]][j-];
            }else break;
        }
    }int x0=read();double min1=;int ans=;
    for (int i=;i<=n;++i){a2=b2=;
        double tmp=work(i,x0);
        if (tmp<min1) min1=tmp,ans=i;
    }printf("%d\n",ans);int m=read();
    for (int i=;i<=m;++i){
        int x=read();x0=read();a2=b2=;
        work1(x,x0);
        printf("%d %d\n",a2,b2);
    }
    return ;
}

luogu1081 noip2012開車旅行includedefine inf 0x7fffffffdefine N 1100

include

define inf 0x7fffffff

define N 1100

繼續閱讀

HDU 5199 Gunner

gdb腳本 - 檢視stl變量

<Effectives STL>筆記之在STL容器中删除元素的方法選擇

C++ STL基本容器比較

STL--vector容器STL—vector容器

洪泛路由模拟（Java實作）

STL相關

ZOJ 3804 YY's Minions

【CF 125D】 Two progressions 劃分等差數列

STL六大元件以及互相關系

STL 六大元件概要

初識 STL

STL——deque 雙向隊列

c++中指針的指針和指針的引用的使用

pat（B）1009. 說反話（逆疊代器）

C++ heap學習