贪心 #动态规划

Question

Monocarp 是一家大型 IT 公司的负责人

他有 \(m\) 个项目个项目需要完成，第 \(i\) 个项目的难度为 \(b_i\)

他的团队离有 \(n\) 个程序员，第 \(j\) 个程序员的耐受能力为 \(a_j\)

Monocarp 需要分配这些项目，需要满足

• 每个程序员最多分配 \(1\) 个项目
• 每个项目至少需要分配给一个程序员
• 如果有 \(k\) 个程序员分配给第 \(i\) 个项目，那么每个程序员的容忍值不能小于(可以大于等于) \(\frac{b_i}{k}\)

帮助 Monocarp 有效的分配这些项目，如果有多个答案，输出任意一个即可

\((1 \le n 2\times 10^5; 1 \le m \le 20)\)

Solution

由于一段程序中最弱的那个程序员的 \(a_j\) 不能低于 \(\frac{b_i}{k}\) ，所以贪心的思想，我们把程序员按照 \(a_j\) 从大到小排序后，一段程序的程序员肯定是连续的

然后考虑程序的排序，发现 \(m\) 特别的小，自然而然想到状态压缩DP

定义 \(F[s]\) 表示当前程序的状态是 \(s\) 需要的最少程序员个数（从大到小排序后）

考虑如何转移，对于每个新加进来的项目 \(i\) 下一个状态就是 \(s|(1<<i)\)

那么，对于每个项目，需要从上一个 \(F[s]\) 往后找，找一段区间 \([l,r]\)，使得 \(b[r]>a[i]/(r-l+1)\) ，然后把这个 \(r\) 赋值给 \(F[s|(1<<i)]\) ，此时的时间复杂度是 \(nm\times 2^m\)

考虑如何优化，其实对于每个项目 \(i\) 从第 \(j\) 个程序员开始，到那个程序员结束是可以预处理出来的，因为对于一个区间 \([l,r]\) 当 \(l\) 增加的时候 \(r\) 必然不会减小

题中，我定义了 \(mn[i][j]\) 表示第 \(i\) 个项目，前面的项目已经用了 \(j\) 个程序员的所需程序员最少人数

Code

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5+5;
int N,M;
int F[1<<19+5],mn[25][maxn],lst[1<<19+5];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
    while(ch<='9'&&ch>='0')ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
int a[maxn],id[maxn],b[25],INF;
vector<int> ans[maxn];
bool cmp(int i,int j){return a[i]>a[j];}
int main(){
    // freopen("E.in","r",stdin);
    // freopen("E.out","w",stdout);
    N=read();M=read();
    for(int i=1;i<=N;i++) a[i]=read(),id[i]=i;
    for(int i=1;i<=M;i++) b[i]=read();
    sort(id+1,id+1+N,cmp);
    
    memset(F,127,sizeof F);INF=F[0];
    for(int i=1;i<=M;i++){
        int r=1;
        for(int l=0;l<=N;l++){
            r=max(r,l+1);
            while(r<=N&&a[id[r]]*(r-l)<b[i]) ++r;
            mn[i][l]=(r==N+1?INF:r);
        }
    }
    
    F[0]=0;
    for(int s=0;s<(1<<M);s++)if(F[s]!=INF)
        for(int i=1;i<=M;i++)
            if(!((s>>(i-1))&1)&&F[s|(1<<(i-1))]>mn[i][F[s]]){
                F[s|(1<<(i-1))]=mn[i][F[s]];
                lst[s|(1<<(i-1))]=s;
            }
    
    if(F[(1<<M)-1]==INF){printf("NO\n");return 0;}
    printf("YES\n");
    
    int now=(1<<M)-1;
    while(now){
        int i=__builtin_ctz(now^lst[now]);
        for(int j=F[lst[now]]+1;j<=F[now];j++)
            ans[i+1].push_back(id[j]);
        now=lst[now];
    }
    for(int i=1;i<=M;i++){
        printf("%d",ans[i].size());
        for(int x:ans[i]) printf(" %d",x);
        printf("\n");
    }
    return 0;
}

Summary

• 看到 \(m \le 20\) 自然而然想到状压DP

• __builtin_ctz(x) 返回 \(x\) 的二进制下末尾的 \(0\) 的个数