Nowcoder 2020 Multi University Training Contest 8-K


Problem

Portal


Thoughts

显然最大的人数就为b[1]。
根据题意,若想要上多份菜,菜必须连续,即前缀和。
那么我们求利润最大值,其实就是每次都优先取当前最大的前缀和(一个1尽量携带最大的利润,1没了后面的就没了)即可。


Accepted Code

typedef long long ll;
typedef __int128 Int;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<Int, pair<Int, Int>> pIII;

const double pi = acos(-1.0);
const int maxn = 0x3f3f3f3f;
const int minn = 0xc0c0c0c0;
const int N = 100010;

Int a[N], b[N], s[N];

priority_queue<pIII> pq;

signed main()
{
#ifdef duipai
    freopen("E:\\Computer major\\Algorithm competition\\duipai\\in.txt","r",stdin);
    freopen("E:\\Computer major\\Algorithm competition\\duipai\\out1.txt","w",stdout);
#endif

    Int T;
    read >> T; 

    for(Int t = 1 ; t <= T ; t ++ )
    {
        Int n;
        read >> n;
        for(Int i = 1 ; i <= n ; i ++ )
        {
            read >> a[i];
            s[i] = s[i - 1] + a[i];
        } 
        for(Int i = 1 ; i <= n ; i ++ ) read >> b[i];

        Int cnt = b[1];
        for(Int i = 1 ; i <= n ; i ++ )
        {
            cnt = min(cnt, b[i]); // 前面的没了,后面的也没了 
            pq.push({s[i], {cnt, i}});
        }

        Int ans = 0, pos = n + 1;
        cnt = 0;
        while(!pq.empty())
        {
            auto t = pq.top();
            Int profit = t.first, num = t.second.first, id = t.second.second;
            pq.pop();

            // 此时pos已经被上完了,代表其后面的都没了,同时其前面的菜的cnt,如果小于b[pos]的话,那么pos的cnt就等于前面菜的cnt,那么在上pos这个菜的时候,前面的菜就已经被上完了,那么只有大于b[pos]的话才行。
            if(num <= cnt || pos <= id) continue;

            ans += profit * (num - cnt);
            cnt = num; // 上一个前缀和的数量
            pos = id;
        }

        write << "Case #" << t << ": " << b[1] << " " << ans << endl;
    }    

    return 0;
}

Author: Mrhh
Reprint policy: All articles in this blog are used except for special statements CC BY 4.0 reprint polocy. If reproduced, please indicate source Mrhh !
评论
 Previous
Nowcoder 2020 Multi University Training Contest 8-I Nowcoder 2020 Multi University Training Contest 8-I
ProblemPortal Thoughts我们将每对数,看做一条边,建图。所以我们只用判断图中是否有环,有环就加上连通块的所有节点,否则就加上连通块的结点数-1。 Accpeted Codeconst int N = 2e5 + 10
Next 
Nowcoder 2020 Multi University Training Contest 7-H Nowcoder 2020 Multi University Training Contest 7-H
写在前面,整除分块也叫除法分块。$O(\sqrt{N})$算法详解 ProblemPortal Notices1-N中i能整除k,i的数量为$\lfloor(N)/k\rfloor$。1-N中i-1能整除k,i的数量为$\lfloor(N
  TOC