CF1223G Wooden Raft 题解

· · 题解

CF1223G Wooden Raft

解析

观察一下所求的答案是一个乘积的形式，而 x 和 y 两个量都是自变量，且不好直接计算。但是 x 和 y 的最大值只有 \max\{a_i\}\le5\times10^5，算是一个可以接受的范围。通常我们可以考虑枚举其中一项，推出另外一项的最优情况。

首先枚举 x 是没有前途的。因为首先你要确定 x 的来源，即从一根木棒中取出还是两根木棒取。可以发现取两根木棒枚举的复杂度已经达到了 O(n^2)，没有优化的余地了。

只能枚举 y 了。当 y=i 时，对于长度为 a_i 的木棒，它所能分割出最多的长度为 i 的木棒的段数为 \left\lfloor\dfrac{a_i}{i}\right\rfloor。此时我们要找出两根长度为 x 的木棒，考虑两个来源：

  1. 从一根木棒截取：

对于多余的 a_i\bmod i 的长度，不可以作为 y，一定可以将其纳入 x 的截取范围。对于原本可以作为 y 的一段，如果想要将其变为 x 的一部分，可以整段拿走，否则会多出无用的部分。由于没有找到一种方法说明从长度为 y 的木棒中取出的段数与答案有单调性，于是只能枚举从 y 的木棒中取出多少段。在能取得的段数相同的时候，绝对优先考虑剩余部分较长的木棒。可以发现，截取段数较多的木棒可以选择取出较少的 y 长度的木棒，可以并入截取段数较少的木棒共同选择。通过分析，可以发现取出段数从大到小枚举是比较方便的。

假设完全分割可以得到的长度为 i 的段数为 cnt，当前枚举取出段数为 j，能取出 j 段的木棒长度 a_k\bmod i 后最大的木棒长度为 m，那么此时 x\times y=\min\{cnt-j,\dfrac{j*i+(m\bmod i)}{2}\}\times i。

  1. 从两根木棒截取

同样可以采用和 1 相同的贪心思路，对于分别取出 j 段的两根木棒，优先选择对 i 取模后较大的两根。具体可以参照上面推理或参考代码。需要考虑两种情况：根据模 i 较大的长度取，根据模 i 较小的长度取。

时间复杂度方面，令 m=\max\{a_i\}，枚举取出的段数总次数为 m+\dfrac{m}{2}+\dfrac{m}{3}+\cdots+1\approx m\ln m，时间复杂度即为 O(n+m\ln m)。

#include<iostream>
#include<cstdio>
#include<algorithm>
using std::cin;using std::cout;
constexpr int N=1000006;
int n,a,c[N],pre[N],m,cnt;
long long ans;
inline void max(int x,int y){ans=std::max(ans,1ll*(x>1)*x*y);}
signed main(){
    freopen("poly.in","r",stdin);
    freopen("poly.out","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    cin>>n;for(int i=1;i<=n;++i){cin>>a;++c[a];m=std::max(m,a);}pre[0]=-1;//为了方便计算及查找区间内是否存在木棒，我们对木棒的长度开桶。
    for(int i=1;i<=2*m;++i){
        if(c[i]) pre[i]=i;
        else pre[i]=pre[i-1];
        c[i]+=c[i-1];
    }
    for(int i=2;i<=m;++i){
        cnt=0;
        for(int j=i;j<=m;j+=i) cnt+=(c[j+i-1]-c[j-1])*(j/i); 
        int mx1=0,mx2=0;
        for(int j=m/i;j>=0;--j){
            int L=j*i,R=L+i-1;
            if(pre[R]>=L&&pre[R]%i>mx1%i) mx1=pre[R];
            max(std::min(cnt-j,j*i+mx1%i>>1),i); 
        }
        mx1=0;
        for(int j=m/i;j>=0;--j){
            int L=j*i,R=L+i-1;
            if(mx1&&mx2){
                max(std::min(cnt-2*j-1,j*i+mx1%i),i);
                max(std::min(cnt-2*j,j*i+mx2%i),i);
            }
            if(mx1&&pre[R]>=L&&pre[R]%i>mx2%i){//新取一根
                if(pre[R]%i>=mx1%i){
                    max(std::min(cnt-2*j-1,pre[R]),i);
                    max(std::min(cnt-2*j,j*i+mx1%i),i);
                }else max(std::min(cnt-2*j,pre[R]),i);
          //有些时候另外一种取法可以省略，具体原因呢可以自己分析
            }
            R=pre[R];
            if(R>=L){//多取多好
                if(R%i>=mx1%i){mx2=mx1;mx1=R;}
                else if(R%i>mx2%i) mx2=R;
                R=c[R]-c[R-1]>1?R:pre[R-1];
                if(R>=L&&R%i>mx2%i) mx2=R;
            }
            if(mx1&&mx2) max(std::min(cnt-2*j,j*i+mx2%i),i);
        }
    }
    cout<<ans;
    return 0;
}//第五十四回 史太君破陈腐旧套 王熙凤效戏彩斑衣