思维题——牛客多校第六场D

雨点打透心脏的1/2处 2023-10-11 09:10 7阅读 0赞

这题的不能用二分做，因为不满足单调性的

可以用multiset做

#include<bits/stdc++.h>
    #define ll long long
    #define rep(i,a,b) for(int i=a;i<=b;i++)
    using namespace std;
    const int maxn=200010;
    multiset<int>s;
    multiset<int>::iterator it;
    int a[maxn],T,N,K,C;
    bool check(int Mid)
    {
        s.clear(); int tk=K;
        rep(i,1,N) s.insert(a[i]);
        while(!s.empty()&&tk--){
            int x=Mid;
            while(x){
               it=s.upper_bound(x);
               if(it==s.begin()) break;
               it--;
               x-=*it;
               s.erase(it);
               //cout<<x<<" "<<endl;
            }
           // cout<<"A"<<endl;
        }
        if(!s.empty()) return false;
        return true;
    }
    int main()
    {
        scanf("%d",&T);
        while(T--){
            scanf("%d%d",&N,&K);
            int L=1,R=1000000000,Mid,ans,sum=0;
            rep(i,1,N) scanf("%d",&a[i]),L=max(L,a[i]),sum+=a[i];
            L=max(L,sum/K);
            rep(i,L,R) {
                if(check(i)) {
                    ans=i; break;
                }
            }
            printf("Case #%d: %d\n",++C,ans);
        }
        return 0;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11296250.html

发表评论取消回复

表情：

评论列表（有 0 条评论，7人围观）

还没有评论，来说两句吧...

相关阅读

相关回文树上dfs——牛客多校第六场C

/ set里的一定是本质不同的回文串，所以先建立回文树当a可以通过nxt指针到达b，或者b可以通过fail指针到达a时，a就是b的子串对于回文树里的每个结点u，我们

淩亂°似流年/ 2023年10月11日 09:14/ 0 赞/ 3 阅读

相关第k小团+bitset优化——牛客多校第2场D

模拟bfs，以空团为起点，用堆维护当前最小的团，然后进行加点更新在加入新点时要注意判重，并且用bitset来加速判断和转移构造 include<bits/std

快来打我*/ 2023年10月11日 09:12/ 0 赞/ 4 阅读

相关思维题+贪心——牛客多校第一场C

/ 给定一组n维向量 A=(a1/m,a2/m,a3/m ... an/m), 求另一个n维向量 P=(p1,p2,p3...pn),满足sum{pi}=1,使得ans

以你之姓@/ 2023年10月11日 09:10/ 0 赞/ 20 阅读

相关思维题——牛客多校第六场D

这题的不能用二分做，因为不满足单调性的可以用multiset做 include<bits/stdc++.h> define ll long long

雨点打透心脏的1/2处/ 2023年10月11日 09:10/ 0 赞/ 8 阅读

相关 2019牛客暑期多校训练营（第四场）

Contest Info -------------------- [Contest Link][] <table> <thead> <tr> <t

淡淡的烟草味﹌/ 2023年06月04日 11:58/ 0 赞/ 119 阅读

相关 2019牛客暑期多校训练营第六场

题目链接：[https://ac.nowcoder.com/acm/contest/886\question][https_ac.nowcoder.com_acm_contes

今天药忘吃喽~/ 2021年11月02日 13:38/ 0 赞/ 367 阅读

相关牛客多校第六场记录

A 题意: 垃圾分类思路: 模拟 include <cstdio> include <iostream> include <algorithm>

柔光的暖阳◎/ 2021年10月29日 12:20/ 0 赞/ 260 阅读

相关 2019牛客暑期多校训练营（第五场）

比赛链接：[https://ac.nowcoder.com/acm/contest/885\question][https_ac.nowcoder.com_acm_contes

左手的ㄟ右手/ 2021年10月26日 18:24/ 0 赞/ 370 阅读

相关牛客多校第三场 F Planting Trees

牛客多校第三场 F Planting Trees 题意：求矩阵内最大值减最小值大于k的最大子矩阵的面积题解：矩阵压缩的技巧因为对于我们有用的信息只

淡淡的烟草味﹌/ 2021年10月15日 23:37/ 0 赞/ 263 阅读

相关牛客多校第七场 C Bit Compression 思维

链接：[https://www.nowcoder.com/acm/contest/145/C][https_www.nowcoder.com_acm_contest_145_C

ゝ一世哀愁。/ 2021年09月20日 13:50/ 0 赞/ 309 阅读