A simple Blog for wyx I've been down the bottle hoping.
NOIP2012 D1T3 开车旅行
发表于: | 分类: Oi | 评论:0 | 阅读:139

####md这sb题怎么这么墨迹,在心里默默地骂出题人
咳咳
题目大意:
在一个数轴上,每个点有互不相同的点权,规定两点之间距离为两个的点权的差的绝对值,现在从最左面出发,只能向右走,交替的走次大值和最大值,然后现在问在规定的距离内,两个人向右走,两个人分别能走多少路

$Solution$
~~思博倍增,普及组小孩都会~~
首先,暴力的话可以直接预处理出下一个点能走的最大值和次大值都是谁,然后暴力的走下去。
然后我们发现这个东西可以倍增,我们先维护出一个点能向右走的最大值和次大值,然后我们就可以玩了
用$pos(i,j)$表示从$i$,向后$2^j$步的位置是谁,显然$pos(i,0) = next_{sec}(i).pos(i,1) = next_{fir}(pos(i,0))$,而对于$j>=2$的情况就直接有$pos(i,j) = pos(pos(i,j-1),j-1)$
然后直接倍增,在倍增处理位置的同时维护一下分别走的距离,然后玩一下就行了。

在维护最大值次大值的时候可以用$set$,当然其实也是可以用双向链表的

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <cmath>
const int N = 100000+5;

typedef long long LL;
LL inf = 1e15;
using namespace std;

struct cmps
{
    int val,now,pos;
    cmps () {}
    cmps (LL _val,int _now,int _pos):val(_val),now(_now),pos(_pos){}
    bool operator < (const cmps &z)const
    {
        return now ^ z.now ? now < z.now : val < z.val;
    }
}tmp[5];

struct Lux
{
    int pos;
    int val;
    bool operator < (const Lux & z)const
    {
        return val ^ z.val ? val < z.val : pos < z.pos;
    }
}a[N];

int L[N];
int R[N];
int T[N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int next_Fir[N];
int next_Sec[N];
int next[N][20];
LL   dis[N][20];
LL  disA[N][20];

LL H[N];

bool equal(double A,double B)
{
    return fabs(A-B) < (1e-9)*max(A,B);
}

double calc(double A,double B)
{
    if(equal(B,0))
        return 1e9;
    else return A / B;
}

int main()
{
//  freopen("27.in", "r", stdin);
    int n = read();
    for(int i=1;i<=n;++i) a[i].pos = i ,H[i] =  a[i].val = read();

    sort(a+1,a+n+1);
    for(int i=1;i<=n;++i)
    {
        L[i] = i - 1;
        R[i] = i + 1;
        T[a[i].pos] = i;
    }

    H[0] = H[n+1] = inf;


    for(int t=1;t<=n;++t)
    {
        int tot = 0;
        int i = T[t];
        if(L[i]) tmp[++tot] = cmps(a[L[i]].val,labs(a[i].val - a[L[i]].val),a[L[i]].pos);
        if(L[L[i]]) tmp[++tot] = cmps(a[L[L[i]]].val,labs(a[i].val - a[L[L[i]]].val),a[L[L[i]]].pos);
        if(R[i] <= n) tmp[++tot] = cmps(a[R[i]].val,labs(-a[i].val + a[R[i]].val),a[R[i]].pos);
        if(R[R[i]] <= n) tmp[++tot] = cmps(a[R[R[i]]].val,labs(-a[i].val + a[R[R[i]]].val),a[R[R[i]]].pos);
        if(tot == 0)continue;
        if(tot == 1){next_Fir[a[i].pos] = tmp[1].pos;L[R[i]] = L[i];R[L[i]] = R[i];continue;}
        sort(tmp+1,tmp+tot+1);
        next_Fir[a[i].pos] = tmp[1].pos;
        next_Sec[a[i].pos] = tmp[2].pos;
        L[R[i]] = L[i];
        R[L[i]] = R[i];
    }

    for(int i=1;i<=n;++i)
    {
        next[i][0] = next_Sec[i];
        next[i][1] = next_Fir[next[i][0]];
        dis[i][0] = labs(H[next[i][0]] - H[i]);
        dis[i][1] = dis[i][0] + labs(H[next[i][1]] - H[next[i][0]]);
        disA[i][0] = disA[i][1] = dis[i][0];
    }

    for(int j=2;j<=18;++j)
        for(int i=1;i<=n;++i)
        {
            next[i][j] = next[next[i][j-1]][j-1];
            dis[i][j] = dis[next[i][j-1]][j-1] + dis[i][j-1];
            disA[i][j] = disA[next[i][j-1]][j-1] + disA[i][j-1];
        }

    for(int j=0;j<=18;++j)
        for(int i=1;i<=n;++i)
            if(!next[i][j])
                next[i][j] = n + 1,dis[i][j] = 1e9+5;

    LL lmt = read();

    int pos = 0;
    double ans = 1e16;
    

    for(int i=1;i<=n;++i){
        LL tmp = 0;
        int x = i;
        LL tlmt = lmt;
        LL all = 0;
        for(int j=18;j>=0 && x!=n+1;--j)
            if(lmt >= dis[x][j])
            {
                lmt -= dis[x][j];
                tmp += disA[x][j] ;
                all += dis[x][j];
                x = next[x][j];
            }
        LL tmpB = all - tmp;
        LL tmpA = tmp;
        double tt = calc(tmpA,tmpB);
//      printf("%.2lf\n",tt);
        if(equal(tt,ans))
        {
            if(H[pos] < H[i])
                pos = i;
        }
        else if(tt < ans)
        {
            ans = tt;
            pos = i;
        }
        lmt = tlmt;
    }

    cout << pos << endl;

    int m = read();
    while(m--){
        LL tmp = 0;
        int x = read();
        lmt = read();
        LL all = 0;
        for(int j=18;j>=0 && x!=n+1;--j){
            if(lmt >= dis[x][j])
            {
                lmt -= dis[x][j];
                all += dis[x][j];
                tmp += disA[x][j];
                x = next[x][j];
            }
        //  cout << x << " " << tmp << endl;
        } 
        LL tmpB = all - tmp;
        LL tmpA = tmp;  
        printf("%lld %lld\n",tmpA,tmpB);
    }
}
    

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP