BZOJ 3544: [ONTAK2010]Creative Accounting [set]

给定一个长度为N的数组a和M，求一个区间[l,r]，使得$(\sum_{i=l}^{r}{a_i}) mod M$的值最大，求出这个值，注意这里的mod是数学上的mod

这道题真好，题面连LaTeX都有了....

模意义下最大字段和，求出前缀和然后用$set$找就行了，可以证明要先找比当前数大的

注意前缀和$0$也要加上

#include 
#include 
#include 
#include 
#include 
#include <set>
using namespace std;
typedef long long ll;
const int N=2e5+5;
inline ll read(){char c=getchar();ll x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f;
}
int n;
ll P,a[N],ans;
set S;
set::iterator it;
int main(){freopen("in","r",stdin);n=read();P=read();for(int i=1;i<=n;i++) a[i]=(read()%P+P+a[i-1])%P;for(int i=0;i<=n;i++){it=S.upper_bound(a[i]);if(it!=S.end()) ans=max(ans,a[i]-(*it)+P);else ans=max(ans,a[i]-(*S.begin()));S.insert(a[i]);}printf("%lld",ans);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！