问题 C: 毛三琛subset

时间限制: 1 Sec  内存限制: 512 MB

题面

---

题面谢绝公开。

题解

---

一眼题解随机化，吓够呛。一句话题解：二分答案加剪枝。

外层枚举$x$，然后二分答案暴力$check$。如果当前答案对于x的check失败就continue，

因为在当前的x中不可能找到比当前答案更优秀的解。加clock卡常可以A。

貌似不需要看脸。毕竟我这个非洲人都一遍A了。复杂度$O(np+nlognlogp)$。

代码：（ps.$￥$神指出了我代码的缺陷：其实在外面直接赋值可以少一个$log$，没必要传参进$check$再赋值。）

 

#include<bits/stdc++.h>
#define rint register int
using namespace std;
int n,p,k,a[10004],sum,ans=0x7fffffff,x[10004],cl;
inline bool check(int z,int mid)
{
    int Sum=0,Cnt=1;
    for(rint i=1;i<=n;++i)
    {
        int lin=a[i]+z;
        if(lin>=p)lin-=p;
        if(lin>mid)return false;
        if(Sum+lin>mid)
        {
            Sum=0,Cnt++;
            if(Cnt>k)return false;
        }
        Sum+=lin;
    }
    return true;
}
int main()
{
    srand(time(NULL));
    int cl=clock();
    scanf("%d %d %d",&n,&p,&k);
    for(rint i=1;i<=n;++i)scanf("%d",&a[i]),sum+=a[i];
    for(rint i=0;i<p;++i)x[i]=i;
    random_shuffle(x,x+p);
    for(rint i=0;i<p;++i)
    {
        if(!check(x[i],ans))continue;
        int l=0,r=sum+1;
        while(l<r)
        {
            int mid=(l+r)>>1;
            if(!check(x[i],mid))l=mid+1;
            else r=mid;
        }
        ans=min(ans,l);
        if(clock()-cl>970000)break;
    }
    printf("%d\n",ans);
}

View Code