题目来源：https://ac.nowcoder.com/acm/contest/5673/K
题意：有n道菜，第i道菜的利润为ai，且有bi盘。你要按照下列要求给顾客上菜。
每位顾客至少有一道菜
给顾客上菜时，都必须从第一道菜开始，上连续的编号的菜，例如，你可能给一位顾客 上的菜为第一道，第二道，第三道，但是不能为只上第二道而不上第一道，或者第一道，第三道中间缺少第二道。
求这些菜能够容纳的最大顾客数，并且求出在容纳最多顾客时的利润最大为多少。

解题思路：首先要求最大利润，可以采用贪心策略，在满足条件时，优先选取利润最大的，由于是 1~i的连续的菜，可以先求出前i份菜的利润的前缀和。然后按利润前缀和大小排序，从大到小遍历，对于前n份菜利润为sum的贡献，计算方法可以求出前n种菜剩余的菜的最小的数量min，让答案累加min∗sum,然后将前n种菜的数量都减去min。

关键词：前缀和，贪心算法

/*前缀和*/ 
#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 q,t,l,r,i,j,k;
    cin>>q;
    while(q--)
    {
        memset(a,0,sizeof(a)),memset(b,0,sizeof(b)),memset(s,0,sizeof(s));//置空处理。 
        cin>>n;
        for(i=0;i<n;i++)
        cin>>a[i];
        cin>>b[0];
        for(i=1;i<n;i++) 
        {
            cin>>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;
        }
        cout<<k<<b[0]<<endl;
        if(ans) 
        cout<<ans<<m;
        else
        cout<<m<<endl;
    }
    return 0; 
}