Codeforces Round #277.5 Div. 2 E. Hiking

題目鏈接:http://codeforces.com/contest/489/problem/E

題意

有n個點和L,給定每個點的坐標x[i]和picturesqueness值b[i]
一個人從0點出發,每天走的距離為r[i],每天的frustration值為sqrt(|r[i]-L|)
求這個人從0點出發走過的點的frustration的和與picturesqueness的和的比值最小
輸出走過的點

解法

01分數規劃
設frustration值為A[i],picturesqueness值為B[i],比值為R
C[i]表示第i個點是否走過了,0表示沒有,1表示走過了
R=sigma(A[i]*C[i])/sigma(B[i]*C[i]),求R最小的方案
將上式變形f(R)=sigma(A[i]*C[i])-R*sigma(B[i]*C[i])
如果f(R)<0則表示sigma(A[i]*C[i])/sigma(B[i]*C[i])<R,則有更小的方案
所以二分R,計算出來最小結果即可

class Cf489E {
    static final int N=1005;
    static final double inf=1000000009;
    double x[]=new double[N];
    double b[]=new double[N];
    double f[]=new double[N];
    int path[]=new int[N];
    int n;
    double L;
    boolean cheak(double y) {
        Arrays.fill(f, 0);
        for(int i=1;i<=n;i++) {
            f[i]=inf;
            for(int j=0;j<i;j++) {
                double tmp=f[j]+Math.sqrt(Math.abs(x[i]-x[j]-L))-y*b[i];
                if(tmp<f[i]) {
                    f[i]=tmp;
                    path[i]=j;
                }
            }
        }
        return f[n]<0;
    }
    void get_path(int u) {
        if(u==0) return;
        get_path(path[u]);
        System.out.print(u+" ");
    }
    void solve() {
        Scanner in=new Scanner(System.in);
        Arrays.fill(path,0);
        n=in.nextInt();
        L=in.nextDouble();
        x[0]=0;
        b[0]=0;
        for(int i=1;i<=n;i++) {
            x[i]=in.nextDouble();
            b[i]=in.nextDouble();
        }
        double l=0,r=inf/10;
        for(int i=0;i<50;i++) {
            double m=(l+r)/2;
            if(cheak(m)) {
                r=m;
            }else {
                l=m;
            }
        }
        get_path(n);
        System.out.println();
    }
}