题解：B4228 [常州市程序设计小能手 2024] 盒子

· · 题解

题面

思路

根据题意易得，先装小盒子最划算，而且套娃是允许的，所以被装的盒子也要尽量小。

所以可以先排序，开一个 cnt 数组记录这个盒子装了多少东西，从头到尾遍历盒子，当遍历到 i 号盒子时，查询 i<j\le n 中最小可以装下 i 号盒子的盒子，也就是满足 \frac{a_j}{2} - cnt_j \ge a_i，并在 cnt_j 上加上 a_i，建立一个标记数组，标记可以被装下的盒子。

最后遍历一遍标记数组，如果这个盒子没被标记答案就 +1。

但其实可以优化掉这个标记数组，在遍历盒子时记录也是可以的。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;
int n;
int a[N],cnt[N];
int ans;
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++){
        int j=i+1,flag=0;
        while(j<=n){
            if(a[j]/2-cnt[j]>=a[i]){
                cnt[j]+=a[i];
                flag=1;
                break;
            }
            j++;
        }
        if(!flag) ans++;
    }
    cout<<ans;
    return 0;
}