2020暑期牛客多校第八场（K）Kabaleo Lite（前缀和贪心，大数爆longlong__int128）

Kabaleo Lite

题目大意:

有n道菜，每道菜有a[i]的利润，b[i]的数量，然后有一堆人来吃，要满足以下两个条件

• 必须从第一道菜开始吃
• 吃的菜必须连续

求最多有多少人来吃，和基于最多人来吃的最大利润和。

解题思路：

第一问：最多有多少人来吃，这个问题很简单，即第一道菜的数量a[1]就是来吃的人的最大值。
（如果来吃的人小于a[1]的话，显然不够需要加到a[1].如果来吃的人大于a[1]的话，显然菜不够，要减到a[1]）

第二问：基于最多人来吃的最大利润和，记录一下每道菜的前缀和，然后用贪心计算一下即可，详细解析见代码。

注意答案的数据范围是1e9 * 1e5 * 1e5 = 1e19 超过了longlong，所以用到了int128类型，int128的读入和输出不能用cin或者scanf，必须自定义读入和输出（也就是快读）。

快读模板：

inline __int128 read(){  //__int128 可以换成 int longlong 基于自己的需求即可
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void out(__int128 x){    //输出
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        out(x/10);
    putchar(x%10+'0');
}

Code:

#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
#include<unordered_map>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const int maxn=1e5+7;

inline __int128 read(){
    __int128 x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
inline void out(__int128 x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    if(x>9)
        out(x/10);
    putchar(x%10+'0');
}

ll a[maxn],b[maxn],s[maxn];

int main()
{
    int w,n,l,r;
    w=read();
    int kase=0;
    while(w--)
    {
//        memset(s,0,sizeof s);
//        memset(a,0,sizeof a);
//        memset(b,0,sizeof b);
        __int128 ans;
        s[0]=0;a[0]=0;b[0]=inf;
        n=read();
        for(int i=1;i<=n;i++){
            a[i]=read();
            s[i]=s[i-1]+a[i];
        } 
//        read(b[1]);
        for(int i=1;i<=n;i++){
            b[i]=read();
            b[i]=min(b[i-1],b[i]);        //供应数量最小的菜
        }
        l=r=1;
        ans=b[1]*a[1];                     //基于最多人来吃的最大利润和，第一道菜的利润需要都加上
        while(r<=n){
            while(r<=n&&s[r]<=s[l]) r++;      //前缀和大于零
            if(r==n+1) break;
            ans+=b[r]*(s[r]-s[l]);          //前开后闭区间 ( s[l] , s[r] ]
            l=r; 
        }
        printf("Case #%d: %lld ",++kase,b[1]);
        out(ans);
        printf("\n");
    }


    return 0;
}