原题链接：https://ac.nowcoder.com/acm/contest/5673/K

题目描述

Apollo开设了一家餐馆，该餐馆提供编号为1~n的n种食物，第i种食物的利润为，但食材原料价格可能过高，导致利润可能为负数。某一天，Apollo用第i种食材做了第道菜。
Apollo将为顾客亲自送菜。在送菜过程中Apollo将遵循以下原则：

• 每位顾客至少得到一道菜；
• 每位顾客都应获得从第1种开始的连续种类编号的菜；
• 对于每位顾客，每道菜只能有一碟。

那么问题来了，Apollo的餐馆最多能容纳多少顾客?并且Apollo想知道，在容纳最多顾客时，最大利润为多少。

输入描述

第一行输入一个整数T，表示测试样例的数量；
每个测试样例均以一个整数n开头，表示食物的种类；
接下来的一行输入n个整数，表示第i道菜的利润；
最后的一行输入n个整数，表示第i道菜的数量。

输出描述

对于每个测试样例均以以下形式输出：
Case #x： y z
其中x表示测试样例的编号，y表示最大顾客数，z表示最大利润。

样例

• 输入

  2
  3
  2 -1 3
  3 2 1
  4
  3 -2 3 -1
  4 2 1 2

• 输出

  Case #1: 3 8
  Case #2: 4 13

• 说明

  For test case 1, the maximum number of visitors is 3, one of a possible solution is:
  The first visitor received food 1, the profit is 2.
  The second visitor received food 1, the profit is 2.
  The third visitor received food 1 + food 2 + food 3, the profit is 2 + (-1) + 3.

题解思路

这题其实就是很简单的贪心策略。不难发现，最大顾客数就是 ，而最大利润只要计算前缀和然后取最大值即可，然后就可以出答案。

可能是你把出题人看的太简单了。
仔细一看数据范围，将会发现最大利润可能会达到，会爆long long，所以就需要用高精度。
（注：一般不推荐使用__int128和long double。因为NOI中无法使用带‘_’的内容（除自己定义）。在整数计算中最好不要用浮点数，但这题很奇怪，用long double居然能水过）
（另：Python自带高精，所以学Python的小伙伴直接可以水过）

参考代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=200200;
const int MAXB=10;
const int mod=10000;
struct Food
{
    long long prof,num;
}a[MAXN];
bool cmp(Food x,Food y)
{
    return x.prof>y.prof;
}
struct BigInt
{
    long long a[MAXB];
    BigInt(){}
    BigInt(long long x)
    {
        a[0]=x;
        for(int i=0;i<MAXB-1;i++)
        {
            a[i+1]=a[i]/mod;
            a[i]%=mod;
        }
    }
};
BigInt add(BigInt x,BigInt y)
{
    BigInt ret;
    for(int i=0;i<MAXB;i++)
        ret.a[i]=x.a[i]+y.a[i];
    for(int i=0;i<MAXB-1;i++)
    {
        ret.a[i+1]+=ret.a[i]/mod;
        ret.a[i]%=mod;
    }
    return ret;
}
BigInt multi(BigInt x,BigInt y)
{
    BigInt ret;
    memset(ret.a,0,sizeof(ret.a));
    for(int i=0;i<MAXB;i++)
        for(int j=0;i+j<MAXB;j++)
            ret.a[i+j]+=x.a[i]*y.a[j];
    for(int i=0;i<MAXB-1;i++)
    {
        ret.a[i+1]+=ret.a[i]/mod;
        ret.a[i]%=mod;
    }
    return ret;
}
void printBigInt(BigInt x)
{
    int hv=-1;
    for(int i=MAXB-1;i>=0;i--)
    {
        if(x.a[i])
        {
            hv=i;
            break;
        }
    }
    if(hv>=1)
    {
        if(x.a[hv]>0)
        {
            for(int i=hv;i>0;i--)
                x.a[i]--,x.a[i-1]+=mod;
        }
        else
        {
            for(int i=hv;i>0;i--)
                x.a[i]++,x.a[i-1]-=mod;
        }
        for(int i=0;i<MAXB-1;i++)
            x.a[i+1]+=x.a[i]/mod,x.a[i]%=mod;
        if(x.a[hv]==0)
            hv--;
        printf("%lld",x.a[hv]);
        for(int i=hv-1;i>=0;i--)
            printf("%04lld",abs(x.a[i]));
    }
    else
        printf("%lld",x.a[0]);
}
int main()
{
    long long ans1,ans2,now;
    int T,n,cas=1;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i].prof);
            if(i>=2)
                a[i].prof+=a[i-1].prof;
        }
        for(int i=1;i<=n;i++)
        {
            scanf("%lld",&a[i].num);
            if(i>=2)
                a[i].num=min(a[i].num,a[i-1].num);
        }
        sort(a+1,a+n+1,cmp);
        BigInt ans=BigInt(0);
        now=0;
        for(int i=1;i<=n;i++)
        {
            if(a[i].num>now)
            {
                ans=add(ans,multi(BigInt(a[i].prof),BigInt(a[i].num-now)));
                now=a[i].num;
            }
        }
        printf("Case #%d: %lld ",cas++,now,ans2,ans1);
        printBigInt(ans);
        printf("\n");
    }
}