2020牛客暑期多校训练营（第八场）K Kabaleo Lite

题目大意

有n道菜，第i道菜有bi盘，每盘利润为ai（利润可能为负）。遵循以下规则为每个顾客上菜：
● 每位顾客至少有一道菜。
● 每位顾客都得到从1开始的连续编号的菜，每道菜只吃一盘。
问能容纳的最大的顾客数，已经可赚取的最大利润。

解题思路

出题人：这是一道 简 单 题。
可以发现，i因为所有人都必须吃第一盘菜，所有b[1]就是最大顾客数量。
我们求利润a数组的前缀和为s,从大到小取即可。

AC代码

#include<bits/stdc++.h>
using namespace std;
const long long N=1e5+9,mod=1e14;
long long a[N],b[N],s[N],n,m,ans;
int main()
{
    int T,t,l,r,i,j,k;
    scanf("%d",&T);
    for(k=1;k<=T;k++)
    {
        memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),memset(s,0,sizeof(s));
        scanf("%lld",&n);
        for(i=0;i<n;i++) scanf("%lld",&a[i]);
        scanf("%lld",&b[0]);
        for(i=1;i<n;i++) scanf("%lld",&b[i]),b[i]=min(b[i],b[i-1]);
        s[0]=a[0];
        for(i=1;i<n;i++) s[i]=s[i-1]+a[i];
        l=r=t=ans=0,m=s[l]*b[l];
        while(r<n)
        {
            while(r<n && s[r]<=s[l]) r++;
            if(r==n)break;
            m+=b[r]*(s[r]-s[l]),ans+=m/mod,m%=mod;
            l=r,t=0;
        }
        printf("Case #%d: %lld ",k,b[0]);
        if(ans) printf("%lld%014lld\n",ans,m);
        else printf("%lld\n",m);
    }
}