P15263 [USACO26JAN2] Circle of Cows P 题解

H_dream · 2026-11-12 19:50:15 · 题解

前言

提供一个 O(n^3) 小常数做法，主打一个相信测评机（毕竟还给了 2s 嘛）。

题目大意

给定一个长度为 C 的环，环上有 N 个点。

定义环上两个点的距离 dis(i, j) = \min(p_j - p_i, C - (p_j - p_i))。也就是沿环走的较小值。

对于每个 1\le k\le \lfloor N/2\rfloor，选出 k 对点，每个点最多被选择一次，求每对点之间最小距离的最大值。

思路

考虑贪心。

先考虑比较简单的情况：只有四个点。（蓝线代表选择的点对）

不难发现右图比左图优。 ::::info[证明]{open} 左图贡献：\min(a, b + c + d, c, b + a + d) = \min(a, c)；
右图贡献：\min(a + b, c + d, a + d, b + c)。

因为：

所以：

于是我们得到一个结论：如果把选择的点对连起来，则两条弦相交比不交优。

显然每个点对都相交是最优的。下面我们证明这个状态可达。 ::::info[证明]{open}

当我们把弦从不交改为相交时，根据三角形两边之和大于第三边（图中用数字标出的两个三角形），它们的总长度必然变大。

因为弦的长度不可能一直变大，所以当变到最大时所有弦必然两两相交（注意不需要交于一点）。

考虑直接枚举一条弦，钦定它是最小弦（答案）。考虑如何加入弦可以达到这个最优局面。

设这个最小弦的答案为 d。那么其他所有的弦必须满足下面的条件：

记 x = p_j - p_i，将上面这个式子的 min 拆开移项后得到：

这不就是个窗口吗！滑动窗口直接双指针就可以维护了。具体的，如果 x < d 就移动右指针；如果 x > m - d 就移动左指针。

时间复杂度 O(n^3)，但是实际上还有一个 \frac 1 2 的常数，所以可以轻松跑过。具体实现可以看代码注释。 ::::success[AC Code & record]

// Problem: Luogu P15263
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P15263
// Memory Limit: 256 MB
// Time Limit: 2000 ms

#include<bits/stdc++.h>
bool Mst;
#define H_dream return 0
#define ll long long
using namespace std;
const int N = 1010;
int n, m;
int p[N << 1], ans[N >> 1];
int dis(int l, int r){
    return p[r] - p[l];
}
int Max(int &x, int y){
    return x = max(x, y);
}

bool Med;
int main(){
    cerr << "Memory is " << abs((&Med)-(&Mst)) / 1024.0 / 1024 << "MB.\n";
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> p[i], p[n + i] = p[i] + m;   //断环为链

    for(int i = 1; i <= n; ++i){
        for(int j = i + 1; j <= n; ++j){        //枚举最小弦
            // cerr << "Now is [l,r] = " << i << ' ' << j << '\n';
            int k = 1, d = min(dis(i, j), m - dis(i, j));
            Max(ans[1], d);
            int l = i + 1, r = j + 1;
            //d <= dis(l, r) <= m - d
            while(l != j && r != i + n){
                while(l != j && r != i + n){
                    int now = dis(l, r);
                    if(now > m - d) ++l;        //多了移 l
                    else if(now < d) ++r;       //少了移 r
                    else break;
                }
                if(l == j || r == i + n) break;
                // cerr << l << ' ' << r << '\n';
                Max(ans[++k], d);
                ++l, ++r;       //强制移动一位避免重复选同一个点
            }
        }
    }

    for(int i = 1; i <= (n >> 1); ++i) cout << ans[i] << ' ';

    H_dream;
}

::::