自动搬运

查看原文

来自洛谷，原作者为

	wydqwq 压制、手法、绝境、突破、自我、证明、巅峰、枷锁、答案、依赖、尽头、诠释、冷静、逆境、自信、无限、打破、困局、质疑、逆转、磨炼、极限、止步、假象、结果、终将、问鼎、挣脱、限制、领域、绝巅、过去、诀别

搬运于2025-08-24 21:18:00，当前版本为作者最后更新于2025-04-16 22:27:21，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题面

思路

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

所以可以先排序，开一个 $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;
}