UVALive - 7501、Business Cycle （二分、思维）

题目vj链接

题面：

题意：
给定一个有 $n$n 个节点的环，每个节点有一个权值 $v_i$vi​，初始时我有一个权值 $val$val，且我在 $0$0 号节点以外（走一步到达 $0$0 号节点）。 $n-1$n−1 号节点的下一步是 $0$0 号节点。
我每到达一个节点， $val=max(val+v_i,0)$val=max(val+vi​,0)，即我每到一个节点都加上这个节点的权值，如果当前我的权值为负数，那么就变为 $0$0。

问，我的初始权值至少为多少，才能保证我在 $p$p 步之内的权值能到达 $g$g。
其中 $p$p 步之内包括 $0$0 步和 $p$p 步。

题解：
很显然，我们二分答案，然后检验答案是否符合。
但是这里 $p$p 十分的大，我们不可能去 $O\left(p\right)$O(p) $check$check。
但是注意到，我要走的路径一定是在一个环上的，考虑 $p>2\ast n$p>2∗n 的一般情况。 $p\le 2\ast n$p≤2∗n 直接 $O\left(p\right)$O(p) check即可。

当 $p>2\ast n$p>2∗n 时。
假设当前二分的初始权值为 $mid$mid 。
我们暴力在环上走一圈，记走一圈之后的权值为 $ans1$ans1，在整个过程中产生的最大值为 $maxx$maxx。
如果当前最大值 $maxx>=g$maxx>=g 则可以。
如果当前最大值 maxx<g，且 $ans1\le mid$ans1≤mid 则表明以后的最大值不可能超过 $maxx$maxx 则不可以。

其他情况 ： maxx<g and ans1>mid，我们暴力再在环上走一圈，记再走一圈之后的权值为 $ans2$ans2。整个过程中的最大值为 $maxx$maxx。
如果当前最大值 $maxx>=g$maxx>=g 则可以。
如果当前最大值 maxx<g，且 $ans1=ans2$ans1=ans2 则表明以后依然是重复当前圈的权值，则不可以。

其他情况 : maxx<g and ans2>ans1 ，这种情况表明在初始值为 $ans1$ans1 时，循环过程中已经没有地方的权值会让我的权值变为 $0$0 了。
考虑反证，假设初始值为 $ans1$ans1 时，循环过程中有地方能让我的权值变为0，且 $ans1>mid$ans1>mid ，那么在初始权值为 $mid$mid 的时候肯定也在 $ans1$ans1 情况下权值变为0的地方让我的权值变为 $0$0。那么这样最终应该是 $ans1=ans2$ans1=ans2。

所以现在的差值 $ans2-ans1$ans2−ans1 是转一圈之后每一个位置会净增加的量。

计算 $add=(p-2\ast n)/n\ast (ans2-ans1)$add=(p−2∗n)/n∗(ans2−ans1)。 $add$add 为每个位置至少还要增加的量。
其中 $add$add 有可能爆掉 $longlong$long long

那么我们取 $maxx=max(maxx,maxx+add)，ans2=ans2+add$maxx=max(maxx,maxx+add)，ans2=ans2+add。

此时，我们还剩下 $pmodn$p mod n 步，没有走。此时 $ans2$ans2 就是最后 $pmodn$p mod n 步的初始值，暴力走完即可。

时间复杂度 $O(T\ast nlogn)$O(T∗nlogn)

做题的时候，二分check的返回条件写错了，应该返回 $maxx>=g$maxx>=g，结果写成的 $maxx>=mid$maxx>=mid，调了个寂寞。

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<bitset>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include<set>
#include<ctime>
#define ui unsigned int
#define ll long long
#define llu unsigned ll
#define ld long double
#define pr make_pair
#define pb push_back
#define lc (cnt<<1)
#define rc (cnt<<1|1)
#define len(x) (t[(x)].r-t[(x)].l+1)
#define tmid ((l+r)>>1)
#define fhead(x) for(int i=head[(x)];i;i=nt[i])
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
using namespace std;

const int inf=0x3f3f3f3f;
const ll lnf=0x3f3f3f3f3f3f3f3f;
const double dnf=1e18;
const double alpha=0.75;
const int mod=998244353;
const double eps=1e-8;
const double pi=acos(-1.0);
const int hp=13331;
const int maxn=100100;
const int maxm=100100;
const int maxp=100100;
const int up=1100;

ll a[maxn];
ll n,g,p;

bool check(ll mid)
{
    if(mid>=g) return true;//初始就符合
	
	//开始跑第一圈 
    ll ans1=mid;
    ll maxx=mid;
    for(int i=0;i<n&&i<p;i++)
    {
        ans1=ans1+a[i];
        if(ans1<0) ans1=0;
        maxx=max(maxx,ans1);
    }
    if(p<=n) return maxx>=g;//已经跑完p步 
    if(maxx>=g) return true;//已经符合要求 
    if(ans1<=mid) return false;//之后的maxx一定不优于当前的
	 
    ll ans2=ans1;
    for(int i=0;i<n&&i+n<p;i++)
    {
        ans2=ans2+a[i];
        if(ans2<0) ans2=0;
        maxx=max(maxx,ans2);
    }
    if(p<=2*n) return maxx>=g;//已经跑完p步 
    if(maxx>=g) return true;//已经符合要求 
    if(ans2==ans1) return false;//在初始值ans1，进入循环，答案不会更优
	
	 
    __int128 add=(p-2*n)/n*(__int128)(ans2-ans1);
    if(maxx+add>=g) return true;//当前最大值加上往后每轮增加的值符合要求 
    
    ll x=p%n;
	ans2+=add;//最后x步起始值 
    for(int i=0;i<n&&i<x;i++)
    {
        ans2=ans2+a[i];
        if(ans2<0) ans2=0;
        maxx=max(maxx,ans2);
    }
    return maxx>=g;
}

int main(void)
{
    int tt;
    scanf("%d",&tt);
    int pp=0;
    while(tt--)
    {
        scanf("%lld%lld%lld",&n,&g,&p);
        for(int i=0;i<n;i++)
            scanf("%lld",&a[i]);
            
        ll l=0,r=g;
        ll ans=0,mid;
        while(l<=r)
        {
            mid=(l+r)>>1;
            if(check(mid)) ans=mid,r=mid-1;
            else l=mid+1;
        }
        printf("Case #%d: %lld\n",++pp,ans);
    }
    return 0;
}