Noip 2012 Day 1 T 3ドライブ旅行無題の70点コード(未完成)

タイトルの説明
AさんとBさんは休みを利用して旅行に出かけることにしました.彼らは行きたい都市を1からNまで番号をつけて、番号が小さいです.
都市は番号の大きい都市の西にあって、各都市の海抜の高さが互いに異なっていることを知っていて、都市iの海抜の高さを覚えています
Hi,都市iと都市jとの間の距離d[i,j]は,この2つの都市の標高の差の絶対値,すなわち
d[i,j] = |Hi? Hj|. 旅行中、AさんとBさんは交代で運転し、初日はAさんが運転し、その後は毎日交代します.彼らの計画
一つの都市Sを起点として東へ走り、最大Xキロで旅を終える.AちゃんとBちゃん
Bさんはいつも進行方向に沿って一番近い都市を目的地として選んでいますが、Aさんはいつも
進行方向に2番目に近い都市を目的地として選択(注意:本題では現在の都市から2つの都市までの距離
同じように、海抜の低い都市に近いと考えられています).誰もが自分の原則に従って目的を選択できない場合
都市部や目的地に着くと、走行総距離がXキロを超え、旅行が終わる.
出発する前に、Aさんは2つの問題を知りたいと思っています.
1.与えられたX=X 0に対して、どの都市から出発して、Aちゃんが車で走る道のりの総数とBちゃんが走る
の合計距離の比が最も小さい(小さいBの走行距離が0の場合、このときの比は無限大とみなされ、2つの無限大は等しいとみなされる).複数の都市を出発すれば、Aちゃんが運転する距離の総数とBちゃんが走る距離の総数の比
値が最小であれば、標高が最も高い都市を出力します.
任意に与えられたX=Xiと出発都市Siに対して、小Aが運転する走行距離の総数および小Bが走行する走行距離の総数.
にゅうしゅつりょくけいしき
入力形式:
1行目は、都市の数を表す整数Nを含む.
2行目にはN個の整数があり、2個の整数の間に1つのスペースで区切られ、都市1から都市Nの海を順に表す.
高さ、すなわちH 1,H 2,......,Hnは、Hiごとに異なる.
3行目には整数X 0が含まれます.
第4の挙動は、所与のM群SiおよびXiを表す整数Mである.
次のM行は、1行あたり2つの整数SiとXiを含み、都市Siから最大Xiキロを走ることを示す.
出力フォーマット:
出力共M+1行.
第1行目は、所定のX 0に対して、S 0と番号付けされた都市からAちゃんが車で走行することを示す整数S 0を含む
の総行程と小Bが走行する総行程の比は最小である.
次のM行は、各行に2つの整数を含み、間を1つのスペースで区切って、所与のSiと
Xi下小A走行の走行距離総数と小B走行の走行距離総数.
入出力サンプル
drive1 4 2 3 1 4 3 4 1 3 2 3 3 3 4 3
drive2 10 4 5 6 1 2 3 7 8 9 10 7 10 1 7 2 7 3 7 4 7 5 7 6 7 7 7 8 7 9 7 10 7
drive1 1 1 1 2 0 0 0 0 0
drive2 2 3 2 2 4 2 1 2 4 5 1 5 1 2 1 2 0 0 0 0 0
説明
【入出力サンプル1の説明】
Noip 2012 Day 1 T 3ドライブ旅行(未解決)-酉鬼-Delirium
各都市の標高と2つの都市間の距離を上図に示す.
都市1から出発すれば、到達可能な都市は2,3,4であり、これらの都市と都市1との距離はそれぞれ1,1,2,2であり、
しかし、都市3の標高は都市2より低いため、都市3は都市1に最も近く、都市2は都市から離れていると考えられている.
1は2番目に近いので、Aさんは町へ行きます.都市2に到着した後、前に到着できる都市は3,4で、この2つの都市は
市と都市2の距離はそれぞれ2,1なので、都市4は都市2に一番近いので、Bさんは都市4まで歩きます.城に着く
市4後、前にはもう到着できる都市がないので、旅行は終わりました.
都市2から出発すれば、到達可能な都市は3,4であり、この2つの都市と都市2の距離はそれぞれ2,1であり、
都市3は都市2に2番目に近いので、Aさんは都市3まで行きます.都市3に到着した後、前にまだ旅行していない都市は
4、だから都市4は都市3に一番近いですが、都市4に着くには総距離が2+3=5>3なので、Bさんは
そのままシティ3で旅を終えます.
都市3から出発すれば到着できる都市は4で、都市3から2番目に近い都市はないので旅行
まだ始まっていないうちに終わりました.
都市4から出発すれば到着できる都市がないので、旅はまだ始まっていないうちに終わります.
【入出力サンプル2の説明】
X=7の場合、
都市1からだとルートは1->2->3->8->9、Aちゃんが歩く距離は1+2=3、Bちゃんが歩く
距離は1+1=2です.(都市1の場合、小Aに最も近い都市は2と6ですが、都市2の方が標高が高く、
都市1に2番目に近い都市のため、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は海抜が高いため、第1行動2を出力する.
【データ範囲】
30%のデータに対して、1≦N≦20、1≦M≦20がある.
40%のデータに対して、1≦N≦100、1≦M≦100がある.
50%のデータに対して、1≦N≦100、1≦M≦1000がある.
70%のデータに対して、1≦N≦1000、1≦M≦10000がある.
100%のデータに対して、1≦N≦100000,1≦M≦10000,−1000000000≦Hi≦10000000,
0≦X 0≦10000000,1≦Si≦N,0≦Xi≦10000000,データはHiが互いに異なることを保証する.
現在はo(n^2)の時間複雑度で前処理するだけで70点しか過ぎず、時間があれば満点に変更できるかどうか
70分コード:

#include
#define MAX 0x7fffffff
using namespace std;
int n,h[100005],x0,m;
struct node{
    int to[3],l[3];//      ，                 
}dian[100005];
int aabs(int x)
{
    if(x>=0)return x;
    else return -x;
}
void cl()
{
    for(int i=n-1;i>=1;i--)
    {
        int t1=i+1,s1=aabs(h[i+1]-h[i]),t2=MAX,s2=MAX;
        for(int j=i+2;j<=n;j++)
        {
            int s=aabs(h[i]-h[j]);
            if(selse
            {
                if(s1]=t1;dian[i].l[1]=s1;
        if(t2!=MAX)
        {
            dian[i].to[2]=t2;dian[i].l[2]=s2;
        }
    }
}
double drive(int i,int l,int bj)//    
{
    int ll[3]={0};
    for(int ren=1;i!=0;i=dian[i].to[3-ren],ren=3-ren)
    {
        if((ll[1]+ll[2]+dian[i].l[3-ren])>l)break;
        ll[ren]+=dian[i].l[3-ren];
    }
    if(bj==1) printf("%d %d
",ll[1],ll[2]);
    if(ll[2]==0)return MAX;
    else return (ll[1]*1.000000)/ll[2];
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    scanf("%d",&h[i]);
    cl();
    cin>>x0;
    double mmin=MAX;
    int dd=1;
    for(int i=1;i<=n;i++)
    {
        double kk=drive(i,x0,0);
        if(kkelse if(kk==mmin&&h[i]>h[dd])
        {
            dd=i;
        }
    }
    cout<
"
";
    cin>>m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        drive(a,b,1);
    }
    return 0;
}