【bzoj3544】[ONTAK2010]Creative Accounting 前缀和+STL-set

题目描述

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

输入

第一行两个整数N，M。
第二行N个整数a_i。

输出

输出一行，表示答案。

样例输入

5 13
10 9 5 -5 7

样例输出

题解

前缀和+STL-set

先用前缀和把一段区间变为前缀相减的形式，然后问题就转化为求$min((sum_i-sum_j)\ mod\ M)(j<i)$。

由于运算是在模意义下的，因此$sum_j$应该是$sum_i$的后继，使用set维护。如果没有后继，那么$sum_i$本身就是最大的以i结尾的区间和。

统计一下答案即可。

#include <set>

#include <cstdio>

using namespace std;

typedef long long ll;

set<ll> s;

set<ll>::iterator it;

int main()

{

	int n , i;

	ll m , sum = 0 , x , ans = 0;

	scanf("%d%lld" , &n , &m);

	s.insert(0);

	for(i = 1 ; i <= n ; i ++ )

	{

		scanf("%lld" , &x) , x = (x % m + m) % m , sum = (sum + x) % m;

		it = s.upper_bound(sum);

		if(it != s.end()) ans = max(ans , sum - *it + m);

		else ans = max(ans , sum);

		s.insert(sum);

	}

	printf("%lld\n" , ans);

	return 0;

}

巴特西

【bzoj3544】[ONTAK2010]Creative Accounting 前缀和+STL-set

最新文章

热门文章