「BZOJ3544」[ONTAK2010] Creative Accounting
Description
给定一个长度为N的数组a和M，求一个区间[l,r]，使得(\sum_{i=l}^{r}{a_i}) mod M的值最大，求出这个值，注意这里的mod是数学上的mod
Input
第一行两个整数N，M。
第二行N个整数a_i。
Output
输出一行，表示答案。
Sample Input
5 13
10 9 5 -5 7
10 9 5 -5 7
Sample Output
11
HINT
「数据范围」
N<=200000，M,a_i<=10^18
题解
水水更健康
维护前缀和，对于每个前缀和，用set找第一个其大的数，找不到就取set中最小的数，然后将当前前缀和加入set
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 |
#include<iostream> #include<cstring> #include<cstdio> #include<cstdlib> #include<cmath> #include<algorithm> #include<vector> #include<set> #define ll long long #define inf 1000000000 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n; ll m,ans=-inf,a[200005],s[200005]; set<ll> st; int main() { n=read();m=read(); for(int i=1;i<=n;i++)a[i]=(read()%m+m)%m; for(int i=1;i<=n;i++)s[i]=(s[i-1]+a[i])%m; ll t; st.insert(0); for(int i=1;i<=n;i++) { if(st.upper_bound(s[i])!=st.end()) t=*st.upper_bound(s[i]); else t=*st.begin(); ans=max((s[i]-t+m)%m,ans); st.insert(s[i]); } printf("%lld\n",ans); return 0; } |
计数器 9788301
OI 课件=>
OI 课件=>
为什么ans的初值是0啊，为何不是-inf
你说的很有道理。。。