2020牛客多校第八场K

Kabaleo Lite

Kabaleo Lite

题意

T组样例,每组样例给定n种菜,给出每种菜的盈利数,数量,顾客只能从第一道菜吃起,你可以决定顾客吃到哪。在顾客人数最多的条件下,盈利最多。输出盈利数。

3
2 -1 3 这是盈利数
3 2 1 这是菜数量
所以第一个客人2+(-1)+3=4
第二个2
第三个2
客人数3
最大盈利是8

思路

对a数组做前缀和,下标从0~i,取菜品数量最小值,以前缀和为第一关键字,数量为第二关键字,下标为第三关键字。
这样的话,对这个含有三个关键字的数据排序,如果这个数据的第三关键字(即下标)比前一个小,那么必定不能计数,因为已经被后面那个更大的数给用完了;如果这个数据的第二关键字(即数量)比前一个小,也必不可能计数,因为已经被后面那个更大的数给用完了。

注意题目数据范围可能超过long long,要用__int128

代码
#includebits/stdc++.h
#define ll __int128
#define pii pairll,pairll,ll 
using namespace std;

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 print(__int128 x){
    if(x0){
        putchar('-');
        x=-x;
    }
    if(x9)
        print(x/10);
    putchar(x%10+'0');
}

const ll maxn=1e5+10;
ll a[maxn],b[maxn],c[maxn];
priority_queuepii q;

int main()
{

    ll t;
    t=read();
    ll kk=1;
    while(t--){
        ll n;
        n=read();
        for(ll i=0;in;i++) a[i]=read();
        for(ll i=0;in;i++) b[i]=read();
        for(ll i=0;in;i++){
            if(i) c[i]=c[i-1]+a[i];
            else c[i]=a[i];
        }
        __int128 ans=0;
        ll bb=b[0];
        for(ll i=0;in;i++){
            bb=min(bb,b[i]);
            q.push({c[i],{bb,i}});
        }
        ll cnt=0,pos=n;
        while(!q.empty()){
            ll x=q.top().first,y=q.top().second.first,z=q.top().second.second;
            q.pop();
            if(y=cnt||pos=z) continue;
            ans+=x*(y-cnt);
            cnt=y;
            pos=z;
        }
        cout"Case #";
        print(kk++);
        cout": ";
        print(b[0]);
        cout" ";
        print(ans);
        coutendl;
    }
    return 0;
}

/*
1
3 
1 2 3
3 2 1
*/ 
最新回复(0)
/jishuVIx2_2BiRN7u4V8NdIYUplVLMjz_2F3OroT0QTwbt_2Ba2Irs_3D4794970
8 简首页