题解归档 - cf2234C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf2234C
• 本地来源：problems/cf2234C/idea.md
• 题目链接：https://codeforces.com/contest/2234/problem/C
• 原始标题：cf2234C / cf2234F 思路（用户）

思路

cf2234C / cf2234F 思路（用户）

C（Easy）与 F（Hard）题意相同，仅 (n) 与 (\sum n) 上限不同。

第一版（2026-06-07 22:53:23 北京时间）

图论题，但数据相当弱，(O(n^2)) 暴力枚举也许能过，但不太体面。

二分答案

• 若某个总水位 / 某高度下的配置合法，则在当前约束下「不连通」时的最大值就是答案（待严格化：二分什么、check 什么）
• 合法 ⟺ 每个连通管（隔板 (h_i)）处约束满足

按管（边）想

• 对每条管 (i)（连接 (i) 与 (i+1)）：找该管允许的最低/关键水位
• 再检查相邻另一条管处，对侧水位是否仍满足要求
• 固定某个容器 (w_l=0) 时，沿环传播约束

第二版（2026-06-07 22:57:11 北京时间）— O(n) 双扫

固定 (w_l=0)，顺时针 / 逆时针各扫一遍，维护路径上 (\max h)。

[ w_i = \min(R_i, L_i), \quad R_i/L_i = \text{从 } l \text{ 沿环到 } i \text{ 路径上最大 } h ]

每个 (l) 为 (O(n))，总 (O(n^2))，C 的 (\sum n\le 3000) 足够。

验证

• [x] 官方样例
• [x] 小数据 brute 对拍（gen 中 (h\le 6, n\le 8)）

代码

来源：problems/cf2234C/solution.cpp

/* Author: likely
 * Time: 2026-06-07 22:57:11
**/
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll maxn=3005;
ll h[maxn+5],L[maxn+5],R[maxn+5];
int main(){
    ll t,n,i,j,k,l,u,v,cur,zc,ans;
    cin>>t;
    while(t--){
        cin>>n;
        for(i=1;i<=n;i++) cin>>h[i];
        for(l=1;l<=n;l++){
            for(i=1;i<=n;i++) L[i]=R[i]=0;
            cur=0;
            for(k=1;k<n;k++){
                u=(l-1+k)%n+1;
                v=(l-1+k-1+n)%n+1;
                cur=max(cur,h[v]);
                R[u]=cur;
            }
            cur=0;
            for(k=1;k<n;k++){
                u=(l-1-k+n)%n+1;
                cur=max(cur,h[u]);
                L[u]=cur;
            }
            ans=0;
            for(i=1;i<=n;i++){
                if(i==l) continue;
                ans+=min(L[i],R[i]);
            }
            cout<<ans;
            if(l==n) cout<<"\n";
            else cout<<" ";
        }
    }
    return 0;
}