2016-12-06

UvaLive 7504 Business Cycle【二分+模拟】

题目链接：

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5523

题意：

$n$个数组成一个圆，给定每个数的值$v_i$，从$0$号元素开始加，如果加完一个数后总和变为了负数，则将总和改为0。给定最多加的元素个数$p$，问你初始值最少为多少才能在从$0$开始的$p$个数内加到$g$。
数据范围：$n \le 10^5, 1 \le g,p \le 10^{18}, v_i \le 10^9$

分析：

初始值越大越容易满足答案，所以显然我们可以二分答案。
在判断答案是否合理时，利用到以下性质：

如果在第一圈无法达到答案，那么第二圈结束得到的值要比第一圈的大才有可能达到答案。
第二圈中不能存在因负数而变为0的情况，因为此时第二圈结束得到的值要么跟第一圈值一样，要么比第一圈小。
第二圈中若不存在因负数变为0的情况，那么以后所有圈中必然也不存在，即每一圈的增量保持不变，可以直接计算圈数然后相乘。

利用上述性质直接判断并计算即可，注意最后要处理最后一个整圈和剩下的零头，不能仅仅考虑零头（在这里wa了好久）因为在最后一个整圈的过程中可能加上某个元素后变为$g$，然而这个元素在零头中可能是加不到的。
最最后一定要注意ans += add * (p / n - 3); 会爆$long \ long$

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
ll a[maxn];
ll g, p;
ll n;
bool judge(ll k)
{
	ll ans;
	ll tmp1 = k;
	for(ll i = 0; i < min(p, n); ++i){
		tmp1 += a[i];
		if(tmp1 < 0) tmp1 = 0;
		if(tmp1 >= g) return true;
	}
	if(p <= n) return false;
	ll tmp2 = tmp1;
	for(ll i = 0; i < min(p - n, n); ++i){
		tmp2 += a[i];
		if(tmp2 < 0) return false;
		if(tmp2 >= g) return true;
	}
	if(p - n <= n) return false;
	if(tmp1 >= tmp2) return false;
	ans = tmp2;
	ll add = tmp2 - tmp1;
	if(p >= 3 * n){
		if((g - ans) / add < (p / n - 3)) return true;
		ans += add * (p / n - 3);
		if(ans >= g) return true;
		for(ll i = 0; i < n; ++i){
			ans += a[i];
			if(ans >= g) return true;
		}
	}
	for(ll i = 0; i < p - p / n * n; ++i){
		ans += a[i];
		if(ans >= g) return true;
	}
	return false;
}
int main (void)
{
	int T;scanf("%d", &T);
	for(int tt = 1; tt <= T; ++tt){
		scanf("%lld%lld%lld", &n, &g, &p);
		for(ll i = 0; i < n; ++i){
			scanf("%lld", &a[i]);
		}
		ll l = -1, r = g;
		while(r > l + 1){
			ll mid = (l + r) / 2;
			if(judge(mid)) r = mid;
			else l = mid;
		}
		printf("Case #%d: %lld\n", tt, r);
	}
	return 0;
}