思路:

显然当我们选定一个米仓的位置后,选择的粮田的位置是一段连续区间.

我们不妨枚举枚举所有的粮田区间,于是我们发现在给定粮田区间时,最优的米仓位置必定是中位数,可以\(O(1)\)确定.

若我们枚举所有的区间,则是\(O(R^2)\)的.

于是我们考虑固定区间起点,则需要的花费显然随区间终点右移而单调不减.于是我们二分得到最优的区间终点即可.

时间复杂度\(O(nlogn)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
#define N 100010
int a[N];
LL sum[N];
 
long long getsum(int l,int r){return sum[r]-sum[l-1];}
long long getinterval(int l,int r){
    if(l==r)return 0;
    if((r-l+1)&1){
        int midins=(l+r)>>1;
        return getsum(midins+1,r)-getsum(l,midins-1);
    }
    else{
        int midins=(l+r)>>1;
        return getsum(midins+1,r)-getsum(l,midins);
    }
}
 
int main(){
    int R,L;LL B;scanf("%d%d%lld",&R,&L,&B);
    register int i,j;for(i=1;i<=R;++i)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
     
    int l,r,mid,res=0;
    for(i=1;i<=R;++i){
        l=i,r=R;while(l<r){mid=(l+r+1)>>1;if(getinterval(i,mid)<=B)l=mid;else r=mid-1;}res=max(res,l-i+1);
    }
     
    printf("%d",res);
     
    return 0;
}

思路:

维护一下前缀和对\(M\)取模得到的值.

考虑当一段区间的结尾固定时,如何寻找区间的起始端点才能使得答案最优.

首先是减去一个比当前小的数,为了使答案最大,当然是减去0,也就是用当前的模来更新答案;

其次是减去一个比当前大的数,这个需要加上\(M\),由于贪心的使答案最大,我们就减去一个之前出现过的比当前大的最小的模来更新答案.这东西用一个set维护就行.

然后我被迷の卡常数了QoQ.

这样写:upper_bound(s.begin(),s.end(),sum[i])就TLE.(T的不是一点半点)

这样写:s.upper_bound(sum[i])就AC.

这TM是什么鬼?

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<set>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long LL;
 
namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Getunsign(T&x){
        int c;while(!isdigit(c=getc()));x=c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sign=c=='-';
        x=sign?0:c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
        if(sign)x=-x;
    }
}
 
#define N 200010
LL a[N],sum[N],p;
set<LL>s;
 
int main(){
    //freopen("tt.in","r",stdin);
    using namespace Fio;
    int n;Getunsign(n);Getunsign(p);
    register int i,j;for(i=1;i<=n;++i){Get(a[i]),a[i]%=p;if(a[i]<0)a[i]+=p;}
    for(i=1;i<=n;++i){sum[i]=sum[i-1],sum[i]+=a[i];if(sum[i]>=p)sum[i]-=p;}
     
    LL nowans=-1;
    for(i=1;i<=n;++i){
        if(sum[i]>nowans)nowans=sum[i];
        set<LL>::iterator it=s.upper_bound(sum[i]);
        if(it!=s.end()&&nowans<sum[i]-*it+p)nowans=sum[i]-*it+p;
        s.insert(sum[i]);
    }
     
    printf("%lld",nowans);
     
    return 0;
}