[CF1303D] Fill The Bag

Solution

考虑从低位往高位贪心，设当前在处理第 \(i\) 位，更低位剩余的部分一共可以拼出 \(cnt\) 个 \(2^i\)

如果 \(n\) 的这一位是 \(1\) ，那么这一位就需要处理

如果 \(cnt>0\)，那么直接从 \(cnt\) 里拿一个，答案不变
否则，暴力向更高位找到最小的那一个，比如它在 \(j\) 位，那么将 \(a_j\) 减 \(1\)，同时将 \(a_{j-1},...,a_{i}\) 都加上 \(1\)，并且答案增加 \(j-i\)

做完每一位后，维护一下 \(cnt\) 即可

（过晚了一分钟）

#include <bits/stdc++.h>

using namespace std;

#define int long long

int T,n,m,t,a[66],cnt;

signed main() {

    ios::sync_with_stdio(false);

    cin>>T;

    while(T--) {

        cin>>n>>m;

        memset(a,0,sizeof a);

        int sum=0;

        for(int i=1;i<=m;i++) {

            cin>>t;

            for(int j=0;j<63;j++) {

                if(t==(1ll<<j)) a[j]++;

            }

            sum+=t;

        }

        cnt=0;

        int ans=0,fg=0;

        if(sum<n) fg=1;

        for(int i=0;i<63;i++) {

            if((n & (1ll<<i))) {

                if(cnt>0) --cnt;

                else if(a[i]>0) {

                    --a[i];

                }

                else {

                    int j=i+1;

                    while(a[j]==0 && j<63) ++j;

                    if(j==63) {

                        fg=1;

                        break;

                    }

                    else {

                        ans+=j-i;

                        a[j]--;

                        for(int k=i;k<j;k++) a[k]++;

                    }

                }

            }

            cnt+=a[i];

            cnt/=2;

        }

        if(fg) cout<<"-1"<<endl;

        else cout<<ans<<endl;

    }

}

巴特西

[CF1303D] Fill The Bag - 贪心

Solution

最新文章

热门文章