P3137[USACO16FEB]Circular Barn S/G
Zelotz
·
·
题解
题目链接
本蒟蒻的第一篇题解，写得不好请指出，蟹蟹。
题意：
有 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} 来存每一个房间里的奶牛。
然后注意下一个房间 $\bmod n$ 就行了。
```cpp
#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$，那就是整个和减去全部的最小字段和。
最小字段和可以把所有元素取反，求最大子段和。
把两种情况取最大值即为答。
这样可以通过加强版的数据了。
### 代码：
```cpp
#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;
}
```
这个方法有点麻烦，比其他大佬的方法菜，不过我也是因为看不懂才来写的。