$皇帝的烦恼$皇帝的烦恼

题目描述见链接 .

$正解部分$正解部分

当是一条链时, 答案显然为 $\max \left(A\right[i-1]+A[i\left]\right)$max(A[i−1]+A[i]), 但这是一个环, 需要考虑 $A_1$A1​ 与 $A_n$An​ 的冲突关系 .

首先答案具有 单调性, 考虑二分答案, 二分出答案设为 $mid$mid, 然后是 $check\left(\right)$check() 部分 .
再设 $A_n$An​ 与 $A_1$A1​ 的 最小集合交 大小为 $min\_inte\left[n\right]$min_inte[n], 我们的目标是使得 $min\_inte\left[n\right]$min_inte[n] 尽量小,
现在与 $A_1$A1​ 不相交的集合 $S$S 大小为 $mid-A_1$mid−A1​,
再考虑到 $A_{n-1}$An−1​ 对 $A_n$An​ 的影响, 可选且与 $A_1$A1​不相交 的 集合大小 为 $\mid S\mid =mid-(A_1\cup A_{n-1})$∣S∣=mid−(A1​∪An−1​) .

$S$S 中的集合显然都应该加入到 $A_n$An​ 中, 然后若还不够, 就只能使用与 $A_1$A1​ 冲突且不与 $A_{n-1}$An−1​ 冲突的集合了, 这会增加 $min\_inte\left[n\right]$min_inte[n] 的值 .
所以 $\mid S\mid$∣S∣ 越大越好, 进而 $A_1\cup A_{n-1}=A_1+A_{n-1}-(A_1\cap A_{n-1})$A1​∪An−1​=A1​+An−1​−(A1​∩An−1​) 越小越好, 再进而 $A_1\cap A_{n-1}$A1​∩An−1​ 越大越好,

为了达到这个目的, 设 $max\_inte\left[i\right]$max_inte[i] 表示 $A_i\cap A_1$Ai​∩A1​ 的最大值, 则通过类似上方的分析, 可以得到以下状态转移方程,

$min\_inte\left[i\right]=\max (0,A_i-(mid-A_{i-1}-A_1+max\_int{e}_{i-1}\left)\right)$min_inte[i]=max(0,Ai​−(mid−Ai−1​−A1​+max_intei−1​))
$max\_inte\left[i\right]=\min (A_i,A_1,(mid-A_{i-1})\cap A_1=A_1-min\_int{e}_{i-1})$max_inte[i]=min(Ai​,A1​,(mid−Ai−1​)∩A1​=A1​−min_intei−1​) .

二分界限为 $[0,3\ast A_{max}]$[0,3∗Amax​], 时间复杂度 $O\left(Nlog{A}_{max}\right)$O(NlogAmax​) .

$实现部分$实现部分

有 $2$2 个要注意的点

1. 关于 $A_1$A1​ 与 $A_2$A2​ 的 $max\_inte,min\_inte$max_inte,min_inte 要特殊处理 .
2. 在检查 $mid$mid 是否可行时, 需要先检查是否 $mid>\max (A_i+A_{i-1})$mid>max(Ai​+Ai−1​) .

#include<bits/stdc++.h>
#define reg register

const int maxn = 1e5 + 10;

int N;
int Ans;
int Max_A;
int A[maxn];
int min_inte[maxn];
int max_inte[maxn];

bool chk(int mid){
        min_inte[1] = max_inte[1] = A[1];
        for(reg int i = 1; i < N; i ++) if(A[i] + A[i+1] > mid) return false;
        for(reg int i = 2; i <= N; i ++){
                min_inte[i] = std::max(0, A[i] - (mid-A[i-1]-A[1]+max_inte[i-1]));
                min_inte[i] = std::min(min_inte[i], A[i]);
                max_inte[i] = std::min(A[1], A[1] - min_inte[i-1]);
                max_inte[i] = std::min(max_inte[i], A[i]);
                if(i == 2) min_inte[i] = max_inte[i] = 0;
// printf("%d: %d %d\n", i, min_inte[i], max_inte[i]);
        }
        return !min_inte[N];
}

int main(){
        scanf("%d", &N);
        for(reg int i = 1; i <= N; i ++) scanf("%d", &A[i]), Max_A = std::max(Max_A, A[i]);
        if(N == 1){ printf("%d\n", A[1]); return 0; }
        int l = 0, r = 3*Max_A;
        Ans = 0x3f3f3f3f;
        while(l <= r){
                int mid = l+r >> 1;
                if(chk(mid)) Ans = std::min(Ans, mid), r = mid - 1;
                else l = mid + 1;
        }
        printf("%d\n", Ans);
        return 0;
}