ARC117 - Gateau

Posted on Edited on In

ARC117 - Gateau

题目大意：给定一个长度为 \(2n\) 的非负环序列 \(x_0,x_1,\cdots x_{2n-1}\) ，以及 \(2n\) 条限制，每条都是

\(\forall A_i,\sum_{j=0}^{n-1} x_{i+j\mod 2n}\ge A_i\)

求最小化 \(\sum x_i\)

\[ \ \]

转化为前缀和作差之后，令人联想到差分约束，但是难以处理跨过环末的限制

于是二分答案 \(s=x_{2n-1}\) ，建立最长路图

\(\forall i<n,dis_{i+n}\ge dis_{i}+A_i\)

\(\forall i\ge n,dis_{i-n}\ge dis_{i}+A_i-s\)

\(\forall i<2n-1,dis_{i+1}\leq dis_i\)

那么无解的条件就是：存在正环或者求得 \(dis_{2n-1}>s\)

自然无法直接通过 \(\text{SPFA}\) 来跑。。。

考虑所有的边构成了一条 \(0-2n-1\) 的零链 和若干极小的二元环

如果二元环出现正环则无解，否则任意一条最长路路径总是可以描述为

\(i<j<n , i(+n)\rightarrow j(+n)\)

在中间点 \(k\) 可以选择花费0的代价向后走，或者

\(k<n:k\rightarrow k+n,cost=A_k\)

\(k\ge n:k\rightarrow k-n,cost=A_k-s\)

也就是在 \(k,k+n\) 之间反复横跳，由此发现一条路径就是

从 \(0-n-1\) 进行扫描，并且允许中间 \(\pm n\) 横跳

（当然这里漏掉了一个特殊边，即 \(dis_{n}\ge dis_{n-1}\) ，这是构成环的边）

这样写出一个变种的 \(\text{Bellman Ford}\) ，由于图的特殊性，只需要常数轮即可确定正环

具体的，当图上不存在正环时，扫描最多经过一次环就会停止更新

也就是这样横跳的扫描更新只会进行常数轮（2轮？）

如果若干轮后依然在更新，说明出现了正环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair <int,int> Pii;
#define reg register
#define mp make_pair
#define pb push_back
#define Mod1(x) ((x>=P)&&(x-=P))
#define Mod2(x) ((x<0)&&(x+=P))
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
int cmax(int &a,int b){ return a<b?a=b,1:0; }

char IO;
template <class T=int> T rd(){
	T s=0; int f=0;
	while(!isdigit(IO=getchar())) f|=IO=='-';
	do s=(s<<1)+(s<<3)+(IO^'0');
	while(isdigit(IO=getchar()));
	return f?-s:s;
}

const int N=3e5+10,INF=1e9+10;

int n;
int A[N],dp[N];

int Check(int s) {
	rep(i,0,n-1) if(A[i]+A[i+n]-s>0) return 0;
	rep(i,0,n*2-1) dp[i]=0;
	dp[n*2-1]=s;
	int f=0;
	rep(k,0,5) { 
		f=0;
		rep(i,0,n-1) {
			f|=cmax(dp[i+n],dp[i]+A[i]);
			f|=cmax(dp[i],dp[i+n]+A[i+n]-s);
			if(i<n-1) {
				f|=cmax(dp[i+1],dp[i]);
				f|=cmax(dp[i+n+1],dp[i+n]);
			}
		}
		f|=cmax(dp[n],dp[n-1]);
	}
	if(f || dp[n*2-1]>s) return 0;
	return 1;
}

int main() {
	n=rd();
	rep(i,0,n*2-1) A[i]=rd();
	int res=-1;
	for(int l=0,r=1.05e9,mid;l<=r;) Check(mid=(l+r)>>1)?r=mid-1,res=mid:l=mid+1;
	printf("%d\n",res);
}