题解 P1956 【Sum_NOI导刊2009提高（5）】

· · 题解

数据水炸的一道题

以至于我拿一个卡时的暴力过掉了还拿了rk1???

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int s[200000],a[200000],ans=1e9+7,kkk=0,n,k,p;
int getin()
{
    int x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x;
}
int rem(int a,int b)
{
    a-=b;
    if(a<0)a+=p;
    return a;
} 
int main()
{
    n=getin(),k=getin(),p=getin();
    for(int i=1;i<=n;i++)a[i]=getin()%p,s[i]=(s[i-1]+a[i])%p;
    for(int i=0;i<n&&kkk<=4500000;i++)
        for(int j=i+1;j<=n;j++)
        {
            int d=rem(s[j],s[i]);
            if(d>=k&&d<ans)ans=d;
            kkk++;
        }
    cout<<ans<<endl;
}

最终版本的卡时肯定有大爷能卡进100ms

还是来说(可能的不过我觉得补星)正解

首先前缀和一下顺便取模

然后可以发现我们要求的就是s_j-s_i或者s_j-s_i+p(以下省略后者，式子肯定都会化,取个min就行了)

因为要不小于k，所以减去一个k变成

min\{s_j-s_i-k|s_j-s_i-k>=0,j>i\}

假设已知s_j,那么就是要找一个最大的s_i使s_j>=s_i+k

这个东西看起来就是一个前驱的样子了

所以可以二叉查找树解决

为什么不用平衡树？

因为不好写随机数据显然二叉查找树的复杂度可以保证不然暴力怎么能过

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int ch[200000][2],f[200000],rt,id,w[200000]={1e9+7},m,opt,x,ans=1e9+7,s[200000],n,k,p;
int prep(int x)
{
    int lst=0,o=rt;
    while(o)
    {
        if(x>w[o])lst=o,o=ch[o][1];
        else o=ch[o][0];
    } 
    return w[lst];
}
void ins(int x)
{
    if(!rt){w[++id]=x,rt=id;return;}
    int o=rt,lst;
    while(o)
    {
        lst=o;
        if(x>w[o])o=ch[o][1];
        else if(x<w[o])o=ch[o][0];
        else break;
    }
    if(!o)
    {
        w[o=++id]=x;
        f[id]=lst,ch[lst][x>w[lst]]=id;
    }
}
int getin()
{
    int x=0,f=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')f=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=getchar();
    return x*f;
}
int main()
{
    n=getin(),k=getin(),p=getin();
    for(int i=1;i<=n;i++)s[i]=(s[i-1]+getin())%p;
    ins(s[1]+k);
    for(int i=2;i<=n;i++)
    {
        ans=min(ans,(s[i]-min(prep(s[i]+1),prep(s[i]+p+1))+k+p)%p);
        ins(s[i]+k);
    }
    cout<<ans<<endl;
}