自动搬运

查看原文

来自洛谷，原作者为

	newbiechd AFO

搬运于2025-08-24 21:45:57，当前版本为作者最后更新于2019-01-31 15:50:06，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

[CQOI2012]组装

UPD：感谢 @liyuting_233 ，修正了一个手误。

LG传送门

首先有一个必须要能推的式子：设第$i$种零件选的生产车间位置为$x _ i$，组装车间位置为$x$， 则总的花费为

$$f(x) = \sum \limits _{i = 1} ^ n (x - x_i) ^ 2$$ $$= n x^ 2 - 2 \sum \limits _{i = 1} ^ n x _ i x + \sum \limits _{i = 1} ^ n x _ i ^ 2 $$

这是一个关于$x$的二次函数， 在$x = \frac {\sum \limits _{i = 1} ^n x_i}{n}$时取得最小值$\sum \limits _{i = 1} ^ n x _ i ^ 2 - \frac {\sum \limits _{i = 1} ^ n x _ i} {n}$。做到这步，我们就可以获得前40分，只需要枚举每种零件选的生产车间，复杂度是指数级的。考虑贪心优化枚举的过程。

下面为了表述方便，设$o = \sum \limits _ {i = 1} ^ n x _ i ^ 2$，$e = \sum \limits _{i = 1} ^ n x _ i$。

首先我们对于同一种零件的生产车间按坐标从小到大排序，每次枚举把某种零件的生产车间替换成他的下一个，这样是有一些情况枚举不到的，但事实上我们只要保证可能的情况都枚举到了就行了，于是贪心.

先给出贪心的结论：设一次替换用一个二元组$\{x _ i, y _ i\}(x_i < y_i)$来表示，如果我们先把表示替换的二元组按照$x _ i + y _ i$从小到大排序，这样就一定不会错过最优解。

下面证明这个结论：用反证法，假设我们这样做会错过最优解，那么一定存在$\{x_1, y_1\}$和$\{x_2, y_2\}$表示的替换使得$x_1$和$y_2$是满足最优解的条件，且替换$\{x_1, y_1\}$比替换$\{x_2, y_2\}$先进行。由于$x_1$是满足最优解的条件，而$y_1$不是，那么必有$\frac {e} {n}$（满足最优解的组装车间）$< \frac {x_1+ y_1} {2}$（二者之间线段的中点），这个结论是显然的（可以自己手玩）。同理有$\frac {e} {n} > \frac {x_2 + y_2} {2}$，由此及上式得$x_1 + y_1 > x_2 + y_2$，但我们已经事先排序保证$x_1 + y_1 < x_2 + y_2$，矛盾。

实现起来就非常简单了，每次替换维护$o$和$e$的变化量，再用$o - \frac {e ^ 2} {n}$和$e / n$更新最小值和答案就行了。

#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#define R register
#define I inline
#define B 1000000
#define D double
#define P pair <int, int>
using namespace std;
const int N = 10003;
char buf[B], *p1, *p2;
I char gc() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, B, stdin),p1 == p2) ? EOF : *p1++; }
I int rd() {
    R int f = 0, b = 1;
    R char c = gc();
    while ((c < 48 || c > 57) && c ^ 45)
        c = gc();
    if (c == 45)
        b = 0, c = gc();
    while (c > 47 && c < 58)
        f = f * 10 +(c ^ 48), c = gc();
    return b ? f : ~f + 1;
}
vector <int> f[N];
vector <pair <int, int> > g;
I D pow(D x) { return x * x; }
I int cmp(P x, P y) { return x.first + x.second < y.first + y.second; }
int main() {
    R int n = rd(), m = rd(), i, j, s, x, y;
    D o = 0, e = 0, del, tmp, ans;
    for (i = 1; i <= m; ++i)
        x = rd(), y = rd(), f[y].push_back(x);
    for (i = 1; i <= n; ++i) {
        s = f[i].size(), sort(&f[i][0], &f[i][0] + s);
        for (j = 1; j < s; ++j)
            g.push_back(make_pair(f[i][j - 1], f[i][j]));
    }
    for (i = 1; i <= n; ++i)
        o += pow(f[i][0]), e += f[i][0];
    tmp = o - pow(e) / n, ans = e / n, s = g.size(), sort(&g[0], &g[0] + s, cmp);
    for (i = 0; i < s; ++i) {
        o += pow(g[i].second) - pow(g[i].first), e += g[i].second - g[i].first;
        if ((del = o - pow(e) / n) < tmp)
            tmp = del, ans = e / n;
    }
    printf("%.4lf", ans);
    return 0;
}