题解：P12928 [POI 2022/2023 R2] 伐木工人 / Drwale

· · 题解

这真只是绿吗。

我们会尽量让最后被砍伐的木材长度最大，我们单独把他取出来，记为 mx。

记两个人砍伐剩下的木材时间分别 k 和 A-k-mx，我们不妨令 k \le A-k-mx，还需要有 k+mx\ge A-k-mx，那么最后的最晚时间是 k+mx。

说了这么多，其实最晚时间就是 \min(k,A-k-mx)+mx，这个可以直接背包。

但是朴素背包会超时，考虑二进制优化，算了下复杂度是 A \sqrt A 的，还是会超时。

可以套用容量和价值一样时用的 bitset 来优化，复杂度是 \frac{A \sqrt A}{w} 的，可以通过。

可能有人对为什么二进制优化的背包是复杂度是 A \sqrt A 有疑惑，A 是背包的容量枚举，\sqrt A 是不同的长度种类最多只有 \sqrt A 种，这个可以用等差数列证。

但是二进制优化不是还有 \log 吗，其实二进制优化枚举出来的长度作为一个新的长度，这些长度的种类最多也是有 \sqrt A 种。

代码实现非常简单：

#include<bits/stdc++.h>
// #define int long long
using namespace std;
/*
#pragma region 哈基米
*/
inline int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9'||c<'0') {if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
    return x*f;
}
const int N=1e6+5,V=5e6+5;
int n,mx,ans,tot,a[N],t[V];bitset<V> s;
signed main(){
    // freopen("1.in" ,"r",stdin );
    n=read();s[0]=1;
    for(int i=1;i<=n;i++) t[a[i]=read()]++,mx=max(mx,a[i]);
    t[mx]--;
    for(int i=1;i<V;i++) if(t[i]) {
        tot+=t[i]*i;
        for(int k=1;k<=t[i];k<<=1) t[i]-=k,s|=s<<(i*k);
        if(t[i]) s|=s<<(i*t[i]);
    }
    for(int i=0;i<V;i++) if(s[i]) ans=max(ans,min(i,tot-i)+mx);
    printf("%d\n",ans);
    return 0;
}