prow2012-A3-0008

从 Trac 迁移的文章

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

原文章内容如下：

自然界出题时我验的题目。

题意也记不清了，做法就是列出了方程后，很明显可以按比较法则决定哪些城市用于提升战斗力是最佳的。

{{{

bool comp(int i,int j){
    //return (sum[N]-sum[i-1])*a[j]<(sum[N]-sum[j-1])*a[i];
    return B*(sum[N]-sum[j-1])/a[i]+B/a[i]*(sum[j-1]-sum[i-1])/a[j]*(sum[N]-sum[j-1])
                >=B/a[j]*(sum[N]-sum[j-1]);
}

}}}

比较两个城市优劣的方法，就是以i城市提升战斗力对之后的总获利，j城市提升战斗力对总获利作比较，决定出在i提升是否优于j。

贪心题可以这样比较优劣，如果从方程里没法决定出i j的优劣，那就是其他做法了。




{{{


#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
double sum[110000],a[110000],b[110000];
int Q[110000];
int N;
double B,A;
bool comp(int i,int j){
    //return (sum[N]-sum[i-1])*a[j]<(sum[N]-sum[j-1])*a[i];
    return B*(sum[N]-sum[j-1])/a[i]+B/a[i]*(sum[j-1]-sum[i-1])/a[j]*(sum[N]-sum[j-1])
                >=B/a[j]*(sum[N]-sum[j-1]);
}
int main(){
    int i;
    while(scanf("%d%lf%lf",&N,&B,&A)!=EOF){
        sum[0] = 0;
        for (i=1;i<=N;i++)
            scanf("%lf%lf",&a[i],&b[i]),sum[i] = sum[i-1]+b[i];
        int L =0,R = 0;

        for (i=N;i>=1;i--)
            if ((R==0&&sum[N]-sum[i-1]>a[i])||comp(i,Q[R-1]))
                    Q[R++] = i;

        int t = 0;
        for (i=1;i<=N;i++){
            if (R>0&&i==Q[R-1]) {
                if ((sum[N]-sum[i-1])>a[i]){
                    A+=B/a[i];
                    B = 0;
                }
                R--;
            }
            B+=A*b[i];
        }
        printf("%.2lf\n",B);
    }
}


}}}

自然界出题时我验的题目。

题意也记不清了，做法就是列出了方程后，很明显可以按比较法则决定哪些城市用于提升战斗力是最佳的。

bool comp(int i,int j){
    //return (sum[N]-sum[i-1])*a[j]<(sum[N]-sum[j-1])*a[i];
    return B*(sum[N]-sum[j-1])/a[i]+B/a[i]*(sum[j-1]-sum[i-1])/a[j]*(sum[N]-sum[j-1])
                >=B/a[j]*(sum[N]-sum[j-1]);
}

比较两个城市优劣的方法，就是以i城市提升战斗力对之后的总获利，j城市提升战斗力对总获利作比较，决定出在i提升是否优于j。

贪心题可以这样比较优劣，如果从方程里没法决定出i j的优劣，那就是其他做法了。

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <algorithm>
using namespace std;
double sum[110000],a[110000],b[110000];
int Q[110000];
int N;
double B,A;
bool comp(int i,int j){
    //return (sum[N]-sum[i-1])*a[j]<(sum[N]-sum[j-1])*a[i];
    return B*(sum[N]-sum[j-1])/a[i]+B/a[i]*(sum[j-1]-sum[i-1])/a[j]*(sum[N]-sum[j-1])
                >=B/a[j]*(sum[N]-sum[j-1]);
}
int main(){
    int i;
    while(scanf("%d%lf%lf",&N,&B,&A)!=EOF){
        sum[0] = 0;
        for (i=1;i<=N;i++)
            scanf("%lf%lf",&a[i],&b[i]),sum[i] = sum[i-1]+b[i];
        int L =0,R = 0;
        for (i=N;i>=1;i--)
            if ((R==0&&sum[N]-sum[i-1]>a[i])||comp(i,Q[R-1]))
                    Q[R++] = i;
        int t = 0;
        for (i=1;i<=N;i++){
            if (R>0&&i==Q[R-1]) {
                if ((sum[N]-sum[i-1])>a[i]){
                    A+=B/a[i];
                    B = 0;
                }
                R--;
            }
            B+=A*b[i];
        }
        printf("%.2lf\n",B);
    }
}