首页 > 代码库 > BZOJ 3544 ONTAK 2010 Creative Accounting 贪心+平衡树
BZOJ 3544 ONTAK 2010 Creative Accounting 贪心+平衡树
题目大意:给出一段区间,和一个树p,请找出一段区间,使得这段区间和%p的值最大。
思路:利用前缀和的思想,用set维护出现过的所有的前缀和。对于一个前缀和m来说,如果之前出现过(m + 1) % p是最好的,这样就可以达到最大。所以就找之前出现过比(m + 1)大的数,如果没有就贪心的取begin()。然后更新答案。
负数取模还是要好好搞搞。
CODE:
#include <set> #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define MAX 200010 using namespace std; int cnt; long long src[MAX],p; set<long long> G; int main() { cin >> cnt >> p; long long ans = 0; G.insert(0); for(int i = 1; i <= cnt; ++i) { scanf("%lld",&src[i]); src[i] %= p; if(src[i] < 0) src[i] += p; src[i] = (src[i - 1] + src[i] % p) % p; set<long long>::iterator it = G.lower_bound(src[i] + 1); if(it == G.end()) it = G.begin(); ans = max(ans,(src[i] - *it + p) % p); G.insert(src[i]); } cout << ans << endl; return 0; }
BZOJ 3544 ONTAK 2010 Creative Accounting 贪心+平衡树
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。