Siyuan

「AHOI / HNOI 2017」礼物
「AHOI / HNOI 2017」礼物
扫描右侧二维码阅读全文
31
2019/07

「AHOI / HNOI 2017」礼物

题目链接:LOJ 2020

我的室友最近喜欢上了一个可爱的小女生。马上就要到她的生日了,他决定买一对情侣手环,一个留给自己,一个送给她。每个手环上各有 $n$ 个装饰物,并且每个装饰物都有一定的亮度。

但是在她生日的前一天,我的室友突然发现他好像拿错了一个手环,而且已经没时间去更换它了!他只能使用一种特殊的方法,将其中一个手环中所有装饰物的亮度增加一个相同的整数 $c$(可能是负数)。并且由于这个手环是一个圆,可以以任意的角度旋转它,但是由于上面装饰物的方向是固定的,所以手环不能翻转。需要在经过亮度改造和旋转之后,使得两个手环的差异值最小。

在将两个手环旋转且装饰物对齐了之后,从对齐的某个位置开始逆时针方向对装饰物编号 $1, 2, \dots, n$,其中 $n$ 为每个手环的装饰物个数,第一个手环的 $i$ 号位置装饰物亮度为 $x_i$,第二个手环的 $i$ 号位置装饰物亮度为 $y_i$,两个手环之间的差异值为:

$$ \sum_{i = 1} ^ {n} (x_{i} - y_{i}) ^ {2} $$

麻烦你帮他计算一下,进行调整(亮度改造和旋转),使得两个手环之间的差异值最小,这个最小值是多少呢?

数据范围:$1 \le n \le 5 \times 10 ^4$,$1 \le a_{i} \le m \le 100$。


Solution

我们将答案的式子写出来并展开:

$$ \begin{align*} \text{answer} & = \sum_{i = 1} ^ {n} (x_{i} - y_{i} + c) ^ {2} \\ & = \sum_{i = 1} ^ {n} (x_{i} ^ {2} + y_{i} ^ {2} + c ^ 2 + 2c(x_{i} - y_{i}) - 2 x_{i} y_{i} ) \\ & = \sum_{i = 1} ^ {n} (x_{i} ^ {2} + y_{i} ^ {2}) + nc ^ {2} + 2c \left(\sum_{i = 1} ^ {n} (x_{i} - y_{i}) \right) - 2 \sum_{i = 1} ^ {n} a_{i} b_{i +k} \end{align*} $$

其中 $k$ 为 $b$ 循环位移的长度(需要先把 $b$ 倍长)。

注意到除去 $2 \sum_{i = 1} ^ {n} a_{i} b_{i + k}$ 以外的部分是一个关于 $c$ 的二次函数的最小值是确定的。问题转化为求 $\sum_{i = 1} ^ {n} a_i b_{i + k}$ 的最大值。如果我们把 $a$ 翻转一下,这个式子就是卷积形式。答案就是卷积后最高 $n$ 项的最大值。

时间复杂度:$\mathcal O(n \log n)$。


Code

/* 此处省略多项式模板 */

int main() {
    int n;
    scanf("%d%*d", &n);
    Vec A(n), B(n);
    int ans = 0, sum = 0;
    for (auto &x : A) scanf("%d", &x), ans += x * x, sum -= x;
    for (auto &x : B) scanf("%d", &x), ans += x * x, sum += x;
    int x1 = floor(1.0 * sum / n), x2 = ceil(1.0 * sum / n);
    ans += std::min(n * x1 * x1 - 2 * x1 * sum, n * x2 * x2 - 2 * x2 * sum);
    B.resize(B.size() << 1);
    std::copy(B.begin(), B.begin() + n, B.begin() + n);
    std::reverse(A.begin(), A.end());
    Vec F = A * B;
    int mx = *std::max_element(F.begin() + n - 1, F.begin() + n + n - 1);
    printf("%d\n", ans - (mx << 1));
    return 0;
}

发表评论