题目描述：

分析：

b[1]就是最大顾客数量。然后求盈利的前缀和，从大到小取即可。

在取盈利的过程中记录用掉的份数以及最小份数的下标，不断前移即可。

但是，这题要用高精度，因为会爆long long；

用long double 和 Python 也能水过。

 

 

代码如下：

#include<bits/stdc++.h>
using namespace std;
int t,n;
long double ans;
struct node
{
    long long m;
    long double l;
}c[1000001];
long long a[1000001],b[1000001];
int cmp(node x,node y)
{
    return x.l > y.l;
}
int main()
{
    scanf("%d",&t);
    for (int v=1; v<=t; v++)
    {
        memset(c,0,sizeof(c));
        memset(b,0,sizeof(b));
        memset(a,0,sizeof(a));
        scanf("%d",&n);
        for (int i=1; i<=n; i++) scanf("%lld",&a[i]);
        int minn=1e9+7,mini;
        for(int i=1; i<=n; i++)
        {
            scanf("%lld",&b[i]);
            c[i].l=c[i-1].l+a[i];
            if (minn>b[i]) mini=c[i].m=i,minn=b[i];
            else c[i].m=mini;
        }
        sort(c+1,c+n+1,cmp);
        int f=0;
        int flag=n+1;
        int sum=b[1];
        int k=b[1];
        int i=0;
        while(k>f)
        {
            i++;
            if (b[c[i].m]-f>0 && flag>c[i].m)
            {
                ans+=c[i].l*(b[c[i].m]-f);
                flag=c[i].m;
                f=b[c[i].m];
                b[c[i].m]=0;
            }
        }
        printf("Case #%d: %d %.0Lf\n",v,sum,ans);
        ans=0;
    }
    return 0;
}

View Code

 

版权声明：本文为WWWZZZQQQ原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/WWWZZZQQQ/p/13433668.html