自动搬运

查看原文

来自洛谷，原作者为

	Zelotz **

搬运于2025-08-24 22:18:09，当前版本为作者最后更新于2021-09-28 17:51:34，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目链接

本蒟蒻的第一篇题解，写得不好请指出，蟹蟹。

题意：

有 $n$ 头奶牛，分布在一些房间，某些房间可能有多头牛，要让这些牛按顺时针移动，求使每一个房间刚好有一个奶牛的最小花费。

花费计算：如果一头奶牛穿过了 $d$ 扇门，他消耗的能量为 $d^2$。

分析：

先把这个环看成一条链

首先说一个东西：如果有 $1$ 头奶牛在 $a$ 点，$1$头奶牛在 $b$ 点，还有一个没有奶牛的 $c$ 点，且 $c>b>a$，要想有一头奶牛在 $b$ 点，一头奶牛在 $c$ 点，方案 $a \to b,b \to c$ 比方案 $a \to c$ 好。

很容易知道这是对的，可以设 $x=b-a,y=c-b$，而 $c-a=y+x$，所以 $(x+y)^2=x^2+y^2+2xy>x^2+y^2$。

也就是说在如果一个房间的奶牛的移动算一个移动过程，移动过程中一头奶牛不要越过另一头没有移动的奶牛。

所以可以直接从一个起点开始，如果这个房间里有超过$1$头奶牛，就把这些奶牛移到依次后面每一个的房间的末尾，直到没有多余的奶牛可以移动为止。

留下房间里最后一头奶牛，也就是上一次最后一头牛，每一个房间都这么处理。

为了好写代码，可以留下最后一头牛，把这个房间里多余的奶牛移动到下一个房间，下一个房间再做处理。

问题是起点如何选择。

当一个起点是合法时，$\sum\limits_{i=1}^{n}c_{i} \geqslant i$。

不知道就枚举呗，反正 $n$ 不超过 $1000$。

窝语文不好，只能描述成这样惹。

代码：

为每一个奶牛编号，为 $1 \sim n$。

用 $d_i$ 来表示编号为 $i$ 的奶牛走过的距离。

用 $\texttt{vector}$ 来存每一个房间里的奶牛。

$\texttt{push\_back}$ 把元素 $\texttt{push}$ 到末尾，所以留下最后一个，其他的往下一个房间移动。

然后注意下一个房间 $\bmod n$ 就行了。

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define reg register int
#define msz(a) memset(a, 0, sizeof a);
#define rep1(i, j, n) for (reg i = j; i <= n; ++i)
#define rep2(i, j, n) for (reg i = j; i >= n; --i)
typedef long long LL;
typedef pair <int, int> PII;
const int INF1 = 0x3f3f3f3f, INF2 = 0x7fffffff;
int n, d[1005], ans, nowid, result = INF2;
vector <int> a[1005], b[1005];
bool vis[1005];
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        for (int j = 1; j <= x; ++j) a[i].push_back(++nowid), b[i].push_back(nowid); //编号
    }
    for (int start = 1; start <= n; ++start) {
    	// 枚举起点进行模拟
        for (int now = start; ; ++now) {
            if (now > n) now %= n;
            if (now == start && flg == 0) break;
            if (a[now].empty()) continue;
            flg = 0;
            int sz = a[now].size();
            int p = now + 1;
            if (p > n) p %= n;
            for (int i = 0; i < sz - 1; ++i) {
                a[p].push_back(a[now][i]);
                d[a[now][i]]++;
            }
            int endnum = a[now][sz - 1];
            a[now].clear();
            a[now].push_back(endnum);
        }
        for (int i = 1; i <= n; ++i) {
            if (a[i].size() != 1) { ans = -1; break; } //是否合法
            ans += d[i] * d[i]; //计算
        }
        if (ans ^ -1) result = min(result, ans);
        msz(d); msz(vis); ans = 0;
        for (int i = 1; i <= n; ++i) a[i].clear();
        for (int i = 1; i <= n; ++i)
            for (int j = 0; j < (int)b[i].size(); ++j)
                a[i].push_back(b[i][j]); //还原
    }
    printf("%d", result);
    return 0;
}

$n^2$ 算法可以通过 $1000$ 的数据，那么 $100000$ 的数据怎么办呢。

可以发现枚举 $start$ 会出现许多没用的枚举，那哪个一个 $start$ 可以确保不会出现非法情况呢。

可以大概猜出是最密集的那个地方的开头吧。

就是说最大字段和。

因为全部奶牛的和为 $n$，所以所有 $c_i$ 的和一定是最大子段和 所以要把每一个 $c_i$ 与 $1$ 做差，可以清晰看出最大的字段，再求出最大子段和的起点。

证明也很简单：

设最大子段和的值为 $x$，如果最大子段和不合法，那么在最大子段和之后必然有一个字段的值 $\leqslant -x-1$，由于所有数的和为 $0$，那么在这个字段之后，剩下的那个字段和 $\geqslant 1$。

所以最大子段和的值不为 $x$，矛盾。

这个证明有点。。充分显示出我的菜。

然后就是环状最大子段和惹。

环状最大子段和好像可以用单调队列，但是我用了另一种方法。

分两种情况讨论：

$1$.这个字段没有包含 $c_1$和 $c_n$，那么就是本来的最大子段和。

$2$.字段包含了 $c_1$和 $c_n$，那就是整个和减去全部的最小字段和。

最小字段和可以把所有元素取反，求最大子段和。

把两种情况取最大值即为答。

这样可以通过加强版的数据了。

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long //不开longlong见祖宗
#define mp make_pair
#define reg register int
#define msz(a) memset(a, 0, sizeof a);
#define rep1(i, j, n) for (reg i = j; i <= n; ++i)
#define rep2(i, j, n) for (reg i = j; i >= n; --i)
typedef long long LL;
typedef pair <int, int> PII;
const int INF1 = 0x3f3f3f3f, INF2 = 0x7fffffff;
const int N = 1e5 + 5;
int n, d[N], ans, nowid, result = INF2, maxn, start, f[N], b[N];
vector <int> a[N];
bool vis[N];
signed main() {
    // freopen("P6170_7.in", "r", stdin);
    scanf("%lld", &n);
    for (int i = 1; i <= n; ++i) {
        int x;
        scanf("%lld", &x);
        b[i] = x - 1;
        for (int j = 1; j <= x; ++j) a[i].push_back(++nowid);
    }
    bool flg = 1;
    int m1 = 0, m2 = 0, sum = 0, bg1, st1, st2;
    for (int i = 1; i <= n; ++i) {
        if (f[i - 1] > 0) f[i] = f[i - 1] + b[i];
        else f[i] = b[i], bg1 = i;
        if (f[i] > m1) m1 = f[i], st1 = bg1;
        sum += b[i];
        b[i] = -b[i];
    }
    for (int i = 1; i <= n; ++i) {
        if (f[i - 1] > 0) f[i] = f[i - 1] + b[i];
        else f[i] = b[i];
        if (f[i] > m2) m2 = f[i], st2 = i + 1;
    }
    m2 = sum + m2;
    if (m1 > m2) start = st1;
    else start = st2;
    // 分类讨论最大子段和
    for (int now = start; ; ++now) {
        if (now > n) now %= n;
        if (now == start && flg == 0) break;
        if (a[now].empty()) continue;
        flg = 0;
        int sz = a[now].size();
        int p = now + 1;
        if (p > n) p %= n;
        for (int i = 0; i < sz - 1; ++i) {
            a[p].push_back(a[now][i]);
            d[a[now][i]]++;
        }
        int endnum = a[now][sz - 1];
        a[now].clear();
        a[now].push_back(endnum);
    }
    for (int i = 1; i <= n; ++i) 
        ans += d[i] * d[i];
    printf("%lld", ans);
    return 0;
}

这个方法有点麻烦，比其他大佬的方法菜，不过我也是因为看不懂才来写的。