题解：AT_arc226_b [ARC226B] Bin-ary Packing

_aa_ · 2026-08-10 20:06:32 · 题解

思路

首先，我们看到最大值最小能自然地想到二分答案。此时问题转换，变成了：“n 个容量为 mid 的袋子能否装完这些包裹”。

算法 1

我们发现所有大小都是 2 的次幂，考虑对于每个袋子从大到小枚举包裹大小能装多少装多少。单次 check 复杂度 O(NM) 无法通过。

算法 2

从大到小枚举包裹大小 i，我们可以先计算出所有袋子在空的情况下最多能塞下多少个当前包裹，容易发现这个东西是 n\cdot\lfloor \frac{mid}{i}\rfloor，发现大的可以拆成小的，所以我们维护一下之前放进去的东西能拆成多少个大小为 i 的，每次判一下够不够即可。单次 check 复杂度 O(M) 可以通过。

代码

#include<bits/stdc++.h>
#define int long long 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define pii pair<int,int >
using namespace std;

constexpr int N=3e5+5,M=45,INF=1e18,mod=998244353;
int n,m;
int arr[M];

bool chk(int x){
    __int128_t sum=0;
    for(int i=m-1;i>=0;--i){
        __int128_t now=(__int128_t)n*(x/(1ll<<i))-sum;
        if(now<arr[i])return 0;
        sum=sum+arr[i];
        sum*=2;
    }
    return 1;
}
void sol(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>arr[i-1];
    }
    __int128_t l=0,r=LONG_LONG_MAX;
    int ans=0;
    while(l<=r){
        __int128_t mid=l+r>>1;
        if(chk(mid)){
            r=mid-1;
            ans=(int)mid;
        }
        else l=mid+1;
    }
    cout<<ans<<'\n';
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        sol();
    }
}