2019 ACMICPC沈阳站 L

作者: ffacs 分类: 题目 发布时间: 2019-12-31 03:42

题意

\(n\)堆物品,每堆有\(a_i\)个物品,每次选\(m\)堆各取一个物品,问最多能取多少次

解法

在现场的时候没有思路,或者说是没怎么想,是雷宇辰\(O(n)\)做出来的。在做CF 603(div.2)的时候的A题是这个题的一个弱化版本,于是想起来补这题。

由于没有测试数据,还不知道算法是不是对的

首先,如果\(n < m\) 输出0,接下来考虑\(m \le n\)的情况

先把\(n\)堆按从大到小排序,然后前\(m\)堆不动,用剩下的堆插入到前面的堆中。前面的\(m\)堆可以成几个宽相同,\(a_i\)个高为1的小矩形堆成的大矩形。从低到高,高度相同的m个矩形可以看成是一次选择的方案。可以发现,小的矩形总是能塞到前面的矩形中去,使得不重叠。也就是说,如果前\(m\)个不动的情况下,后面的矩形可以随意加到前面的\(m\)矩形中。这样就可以二分高度了。至于先把前\(m\)个先放好,可以证明不会对最优解产生影响。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <typename T>
inline void read(T &a) {
    T flag = 1,ch;a = 0;
    while ((ch = getchar()) < '0' || ch > '9') if (ch == '-') flag = -1;
    a = ch - '0';
    while ((ch = getchar()) >= '0' && ch <= '9') a = a * 10 + ch - '0';
    a *= flag;
}
const int maxn=3e5+5;
ll a[maxn],n,m,s;
bool check(ll mid){
    ll left=s;
    for(int i=1;i<=m;i++){
        if(a[i]>=mid) continue;
        left-=mid-a[i];
    }11
    if(left<0) return 0;
    return 1;
}
int main(){
    int T;cin>>T;
    while (T--){
        cin>>n>>m;ll sum=0;s=0;
        for(int i=1;i<=n;i++) read(a[i]),sum+=a[i];
        if(n<m) {puts("0");continue;} //spj
        sort(a+1,a+1+n,greater<int>()); // sort from s to g
        for(int i=m+1;i<=n;i++) s+=a[i]; 
        ll l=1,r=sum/m+5;// the max probably ans is sum/m
        while (l+1<r){
            ll mid=(l+r)>>1;
            if(check(mid)) l=mid;
            else r=mid;
        }
        cout<<l<<endl;
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注