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

题目vj链接

题面：

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

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

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

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

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

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

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

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

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

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

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

做题的时候，二分check的返回条件写错了，应该返回 $maxx>=g$，结果写成的 $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; }