2020暑期牛客多校训练营第八场(K)Kabaleo Lite(贪心,高精度)

Kabaleo Lite

原题请看这里

题目描述:

厌倦了无聊的 W F H ( WFH( WFH(在家工作 ) ) ),阿波罗决定开设一家名为 Kabaleo   Lite \textbf{Kabaleo Lite} Kabaleo Lite的快餐店
该餐厅提供 n n n种食物,编号从 1 1 1 n n n。第 i i i种食物的利润为 a i a_i ai。利润可能为负,因为它使用了昂贵的原料。在第一天,阿波罗准备了第 i i i种食物的 b i b_i bi菜肴。
阿波罗餐厅的独特之处在于订购食物的过程。阿波罗亲自为每个访客选择了一组该访客将获得的菜肴。这样做时,阿波罗遵循以下规则:

  • 每位访客应至少获得一道菜。
  • 从第一个食物开始,每个访客都应获得连续的食物。每种食物的访客都会得到一盘正餐。

例如,游客可能会收到第一类食物的一碟,第二类食物的一碟,第三类食物的一碟。
阿波罗最多可容纳多少访客?而且他想知道最大的访问者可以赚取的最大利润。

输入描述:

输入的第一行给出测试用例的数量 T ( 1 ≤ T ≤ 10 ) \mathbf{T}(1 \leq \mathbf {T} \leq 10) T(1T10)
每个测试用例均以包含一个整数 n ( 1 ≤ n ≤ 1 0 5 ) n(1 \le n \le 10 ^ 5) n(1n105)的行开头,该整数代表不同种类的食物的数量。
第二行包含 n n n个以空格分隔的数字 a i ( − 1 0 9 ≤ a i ≤ 1 0 9 ) a_i(-10 ^ 9 \le a_i \le 10 ^ 9) ai(109ai109),其中 a i a_i ai表示第i种菜肴的利润。
第三行包含 n n n个以空格分隔的数字 b i ( 1 ≤ b i ≤ 1 0 5 ) b_i(1 \le b_i \le 10 ^ 5) bi(1bi105),其中 b i b_i bi表示第i种菜肴的数量。

输出描述:

对于每个测试用例,输出一行,其中包含: C a s e Case Case # x x x y y y z z z,其中 x x x是测试用例编号 ( ( ( 1 1 1开始 ) ) ) y y y是最大访问者数量, z z 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
思路:

贪心+高精度
比赛的时候没想到爆longlong了呜呜呜呜一直WA~~~~
这题…如果不是高精度真没什么好讲的…
很简单的贪心策略:
因为所有人都必须吃第一盘菜,所以 b 1 b_1 b1就是最大的顾客数(啊这…)
所求的利润只要求一下前缀和然后取最大值就可以了…(啊这…)
然后一算数据,发现利润最大值可能达到 1 e 19 1e19 1e19(好赚钱),超longlong了,于是要用高精度,这里写的是压位高精(又臭又长)。

A C AC AC C o d e Code Code:
#includebits/stdc++.h
#define ll long long
using namespace std;
const int MAXN=2e5+5;
const int MAXM=10;
const ll mod=10000;
struct node{ll x,num;}a[MAXN];
bool cmp(node x,node y){return x.xy.x;}
struct bigint{
    ll b[MAXM];
    bigint(){}
    bigint(ll x){
        b[0]=x;
        for(int i=0;iMAXM-1;++i){
            b[i+1]=b[i]/mod;
            b[i]%=mod;
        }
    }
};
bigint add(bigint x,bigint y){
    bigint ret;
    for(int i=0;iMAXM;++i)
        ret.b[i]=x.b[i]+y.b[i];
    for(int i=0;iMAXM-1;++i){
        ret.b[i+1]+=ret.b[i]/mod;
        ret.b[i]%=mod;
    }
    return ret;
}
bigint mul(bigint x,bigint y){
    bigint ret;
    memset(ret.b,0,sizeof(ret.b));
    for(int i=0;iMAXM;++i)
        for(int j=0;i+jMAXM;++j)
            ret.b[i+j]+=x.b[i]*y.b[j];
    for(int i=0;iMAXM-1;++i){
        ret.b[i+1]+=ret.b[i]/mod;
        ret.b[i]%=mod;
    }
    return ret;
}
void printbigint(bigint x){
    int hv=-1;
    for(int i=MAXM-1;i=0;--i)
        if(x.b[i]){hv=i;break;}
    if(hv=1){
        for(int i=hv;i0;--i){
            if(x.b[hv]0){x.b[i]--;x.b[i-1]+=mod;}
            else{x.b[i]++;x.b[i-1]-=mod;}
        }
        for(int i=0;iMAXM-1;++i){
            x.b[i+1]+=x.b[i]/mod;
            x.b[i]%=mod;
        }
        if(!x.b[hv]) hv--;
        printf("%lld",x.b[hv]);
        for(int i=hv-1;i=0;--i)
            printf("%04lld",abs(x.b[i]));
    }
    else printf("%lld",x.b[0]);
}
ll now;
int t,n;
int main(){
    scanf("%d",t);
    for(int Case=1;Case=t;++Case){
        scanf("%d",n);
        for(int i=1;i=n;++i){
            scanf("%lld",a[i].x);
            if(i=2) a[i].x+=a[i-1].x;
        }
        for(int i=1;i=n;++i){
            scanf("%d",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].numnow){
                ans=add(ans,mul(bigint(a[i].x),bigint(a[i].num-now)));
                now=a[i].num;
            }
        printf("Case #%d: %lld ",Case,now);
        printbigint(ans);
        puts("");
    }
}
最新回复(0)
/jishu_2BiMt7V0k7zxOQTMpySug43FacBpItuw3dFAL_2BlHQC_2Bw_3D4794968
8 简首页