题解归档 - cf2229F

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2229F
• 本地来源：problems/cf2229F/idea.md
• 题目链接：https://codeforces.com/contest/2229/problem/F
• 原始标题：cf2229F

思路

cf2229F

pattern: last job of the overloaded bucket + subset partition.

claim: In an optimal order, focus on the bucket that attains the final maximum and on the last item placed into it. If its final item is the largest item of a target subset G, then before that item the same bucket has load sum(G)-max(G), and every other bucket must have load at least that value.

necessary: Therefore the complement of G must be splittable into k-1 groups, each with sum at least sum(G)-max(G).

sufficient: If such a split exists, first realize those k-1 groups while the target bucket accumulates G without its largest item; then place the largest item of G into a minimum bucket.

search: Enumerate target subsets by decreasing sum(G). For each, test whether the complement can cover k-1 groups of threshold sum(G)-max(G) by memoized submask recursion. The first feasible target sum is the answer.

brute/check: The brute enumerates all permutations for n<=8 and simulates the greedy assignment.

edge: k=1 gives the total sum.

代码

来源：problems/cf2229F/solution.cpp

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxm=(1<<18)+5;
ll a[25],sum[maxm],mx[maxm],cnt[maxm],ord[maxm],n,k,lim,pp;
unordered_map<ll,ll>mp;
bool cmp(ll x,ll y){
    return sum[x]>sum[y];
}
ll can(ll mask,ll g){
    ll key,lb,rest,sub,cur;
    if(g==0) return 1;
    if(pp==0) return 1;
    if(cnt[mask]<g) return 0;
    if(sum[mask]<pp*g) return 0;
    if(g==1) return sum[mask]>=pp;
    key=mask*25+g;
    if(mp.find(key)!=mp.end()) return mp[key];
    lb=mask&-mask;
    rest=mask^lb;
    sub=rest;
    while(1){
        cur=sub|lb;
        if(sum[cur]>=pp and cnt[mask^cur]>=g-1 and sum[mask^cur]>=pp*(g-1)){
            if(can(mask^cur,g-1)) return mp[key]=1;
        }
        if(sub==0) break;
        sub=(sub-1)&rest;
    }
    return mp[key]=0;
}
int main(){
    ll t,i,mask,lb,p,pre,full,ans,need,other;
    scanf("%lld",&t);
    while(t--){
        scanf("%lld%lld",&n,&k);
        for(i=1;i<=n;i++) scanf("%lld",&a[i]);
        full=(1<<n)-1;
        sum[0]=mx[0]=cnt[0]=0;
        for(mask=1;mask<=full;mask++){
            lb=mask&-mask;
            p=__builtin_ctz((unsigned)lb)+1;
            pre=mask^lb;
            sum[mask]=sum[pre]+a[p];
            mx[mask]=max(mx[pre],a[p]);
            cnt[mask]=cnt[pre]+1;
        }
        if(k==1){
            printf("%lld\n",sum[full]);
            continue;
        }
        for(mask=1;mask<=full;mask++) ord[mask]=mask;
        sort(ord+1,ord+full+1,cmp);
        ans=0;
        for(i=1;i<=full;i++){
            mask=ord[i];
            if(sum[mask]<=ans) break;
            need=sum[mask]-mx[mask];
            other=full^mask;
            if(need==0){
                ans=sum[mask];
                break;
            }
            if(cnt[other]<k-1) continue;
            if(sum[other]<need*(k-1)) continue;
            pp=need;
            mp.clear();
            if(can(other,k-1)){
                ans=sum[mask];
                break;
            }
        }
        printf("%lld\n",ans);
    }
    return 0;
}