prow2012-A3-0023

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

贪心分配位置，取中位数做就是了。

{{{


#include <algorithm>
#include <stdio.h>
using namespace std;
#define maxn 101000
long long A[maxn],B[maxn],X[maxn],high[maxn];
bool cmp(int i,int j){
    if (A[i]==A[j]) return B[i]<B[j];
    else return A[i]<A[j];
}
int Left[maxn],Right[maxn],order[maxn];
int N,M;
int oo = 1000000000;
int f[maxn],Q[maxn];
int main(){
    int i,j;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++)
            order[i] = i,scanf("%lld%lld",&A[i],&B[i]);
        sort(order,order+N,cmp);
        order[N] = N;
        A[N] = -1;
        int M = 1;
        for (i=0;i<N;i++)
            if (A[order[i]]!=A[order[i+1]])
                X[M] = A[order[i]],high[M++] = B[order[i]];
        N = M;
        int L = 0,R = 0;
        Q[R++] = 1;
        Left[1] = 1;
        for (i=2;i<N;i++)
        {
            Left[i] = i;
            while(L<R&&(X[i]-X[Q[R-1]]<=high[i]))
                R--,Left[i] = Left[Q[R]];
            Q[R++] = i;
        }
        L = R = 0;
        Q[R++] = N-1;
        Right[N-1] = N-1;
        for (i=N-2;i>0;i--){
            Right[i] = i;
            while(L<R&&(X[Q[R-1]]-X[i]<=high[i]))
                R--,Right[i] = Right[Q[R]];
            Q[R++] = i;
        }
       // for (i=1;i<N;i++)
         //   printf("%d :%d %d\n",i,Left[i],Right[i]);
        for (i=0;i<N;i++)
            f[i] = oo;
        f[0] = 0;
        L = 0,R = 0;
        Q[R++] = 0;
        for (i=1;i<N;i++){
            int tmp = -1;
            while(L<R&&Left[i]-1<=Q[R-1])
                R--,tmp = f[Q[R]];
            if (tmp==-1){
                f[i] = min(f[i],f[i-1]+1);
            }else {
                R++;
                f[i] = min(f[i],tmp+1);
            }
            while(L<R&&f[Q[R-1]]>=f[i]) R--; 
            f[Right[i]] = min(f[Right[i]],f[i-1]+1);
            Q[R++] = i;
        }
        printf("%d\n",f[N-1]);
    }
}


}}}

贪心分配位置，取中位数做就是了。

#include <algorithm>
#include <stdio.h>
using namespace std;
#define maxn 101000
long long A[maxn],B[maxn],X[maxn],high[maxn];
bool cmp(int i,int j){
    if (A[i]==A[j]) return B[i]<B[j];
    else return A[i]<A[j];
}
int Left[maxn],Right[maxn],order[maxn];
int N,M;
int oo = 1000000000;
int f[maxn],Q[maxn];
int main(){
    int i,j;
    while(scanf("%d",&N)!=EOF){
        for (i=0;i<N;i++)
            order[i] = i,scanf("%lld%lld",&A[i],&B[i]);
        sort(order,order+N,cmp);
        order[N] = N;
        A[N] = -1;
        int M = 1;
        for (i=0;i<N;i++)
            if (A[order[i]]!=A[order[i+1]])
                X[M] = A[order[i]],high[M++] = B[order[i]];
        N = M;
        int L = 0,R = 0;
        Q[R++] = 1;
        Left[1] = 1;
        for (i=2;i<N;i++)
        {
            Left[i] = i;
            while(L<R&&(X[i]-X[Q[R-1]]<=high[i]))
                R--,Left[i] = Left[Q[R]];
            Q[R++] = i;
        }
        L = R = 0;
        Q[R++] = N-1;
        Right[N-1] = N-1;
        for (i=N-2;i>0;i--){
            Right[i] = i;
            while(L<R&&(X[Q[R-1]]-X[i]<=high[i]))
                R--,Right[i] = Right[Q[R]];
            Q[R++] = i;
        }
       // for (i=1;i<N;i++)
         //   printf("%d :%d %d\n",i,Left[i],Right[i]);
        for (i=0;i<N;i++)
            f[i] = oo;
        f[0] = 0;
        L = 0,R = 0;
        Q[R++] = 0;
        for (i=1;i<N;i++){
            int tmp = -1;
            while(L<R&&Left[i]-1<=Q[R-1])
                R--,tmp = f[Q[R]];
            if (tmp==-1){
                f[i] = min(f[i],f[i-1]+1);
            }else {
                R++;
                f[i] = min(f[i],tmp+1);
            }
            while(L<R&&f[Q[R-1]]>=f[i]) R--; 
            f[Right[i]] = min(f[Right[i]],f[i-1]+1);
            Q[R++] = i;
        }
        printf("%d\n",f[N-1]);
    }
}