第18回日本情報オリンピック 本選 コイン集め 解説

· · 题解

第18回日本情報オリンピック 本選 コイン集め 解説

更好的阅读体验

问题描述

JOI 先生的收藏室里有一张巨大的桌子，上面有许多稀有的硬币。为了清理桌子，他要重新摆放硬币。

桌面可视为 (2\times 10^9+1) \times (2\times 10^9+1) 的网格。网格上往下数第 i 行（-10^9 \le i \le 10^9），左往右数第 j 列（-10^9 \le j \le 10^9）的格子坐标记为 (i, j) 。

JOI 先生有 2N 枚硬币。初始时，第 i 枚 (1 \le i \le 2N) 硬币被放在坐标为 (X_i, Y_i) 的格子里。JOI 先生的目标是在每个满足 1 \le x \le N, 1 \le y \le 2 的格子 (x,y) 上恰好放一枚硬币。为了不损坏硬币，他能做的唯一一个操作是钦定一枚硬币然后将其移动到相邻的一个格子中（我们说两个格子相邻，当且仅当这两个格子有公共边）。在移动硬币的过程中，允许两个硬币处在同一个格子中。JOI 先生希望通过尽量少的操作次数完成目标。

现在给出硬币的数量和初始时所在的位置，编写一个程序，计算完成 JOI 先生目标所需的最少操作次数。

题解

贪心，结论类似于 [JSOI2018]列队 / 均分纸牌。

注意到最后所有的 2 \times N 个棋子都需要移动到左下角 [1,1]，右上角 [2,N] 的矩形中，且每个棋子最终需要占据单独的一个格子，则问题可转化为为每个棋子分配一个格子。

所以 Subtask1 的 8 分，可以通过暴力枚举每一个棋子对应的格子获得。

下面考虑如何分配格子。

如果想要将这些棋子，分配到这连在一起的一个矩形中，那么这些棋子首先需要移动到这个矩形中，显然对于棋子 i(X_i,Y_i)，将其移动到最近的矩形格 (X_i',Y_i') 中最优。

移动顺序显然不影响答案，所以行列分开考虑，分别有以下几种情况：

\begin{cases} X_i & X_i\in[1,n]\\ 1 & X_i \in (-\infty,1)\\ n & X_i \in (n,+\infty) \end{cases} \begin{cases} 1 & Y_i \in (-\infty,1]\\ 2 & Y_i \in [2,+\infty) \end{cases}

将棋子 i 从 (X_i,Y_i) 移动到 (X_i',Y_i') 的代价为 |X_i-X_i'| + |Y_i-Y_i'|

上述移动方法之所以正确，是因为在移动过程中，每个格子可以同时堆放多个棋子。

但是可能存在多个不同的 a_1,a_2,\cdots,a_k，使得

X_{a_1}' = X_{a_2}' = X_{\cdots}' = X_{a_k}'\\ Y_{a_1}' = Y_{a_2}' = Y_{\cdots}' = Y_{a_k}' \end{cases}

假设 f(x,y) 代表满足

\begin{cases} x = X_i\\ y = Y_i \end{cases}(i \in[1,2 \times N]) $ 的 $i$ 的数量。 至此，问题转化为调整矩形里每一个格子的棋子数量。 容易得到贪心算法，从 $1$ 到 $N$ 扫描所有 $f(i,1),f(i,2)

显然，[i,1],[i,2] 位置上需要移走的棋子数量分别为 g(i,1)=f(i,1)-1,g(i,2)=f(i,2)-1（如果为负，则为移来的数量）

分几类讨论：

无答案贡献。

令 p=\min\{g(i,1),-g(i,2)\}，代表从 [i,1] 挪 p 个棋子到 [i,2]。

此后，需要把 g(i,1)-p 个棋子挪到 g(i+1,1)，把 g(i,2)+p 个棋子挪到 g(i+1,2)

第 i 列对答案的贡献为 p + g(i,1) +g(i,2)

同上类。

同上类，只是不需要计算 p，直接向右移动即可。

Code

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

template < typename Tp >
inline void rd(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
    x *= fh;
}

template < typename Tp >
inline void bird(Tp &x) {
    x = 0; int fh = 1; char ch = 1;
    while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if(ch == '-') fh = -1, ch = getchar();
    while(ch >= '0' && ch <= '9') x = x * 2 + ch - '0', ch = getchar();
    x *= fh;
}

template < typename Tp >
inline void smax(Tp &x, Tp y) {
    if(x < y) x = y;
}

const int maxn = 200000 + 7;

int n;
int num[2][maxn];

long long ans;

//#define tester

signed mian(void) {
    #ifdef tester
        freopen("coin.in", "r", stdin);
        freopen("coin.out", "w", stdout);
    #endif
    rd(n);
    for(int i = 1, x, y; i <= n * 2; i++) {
        rd(x); rd(y);
        int sx, sy;
        if(x >= n) sx = n;
        else if(x <= 1) sx = 1;
        else sx = x;
        if(y > 1) sy = 2;
        else sy = 1;
        if(sx > x) ans += sx - x;
        else ans += x - sx;
        if(sy > y) ans += sy - y;
        else ans += y - sy;
        --sy;
        num[sy][sx]++;
    }
    for(int i = 1; i <= n; i++) {
        num[0][i]--, num[1][i]--;
        int RIP = 0;
        if(num[0][i] > 0 && num[1][i] < 0) RIP = min(num[0][i], -num[1][i]);
        else if(num[0][i] < 0 && num[1][i] > 0) RIP = min(-num[0][i], num[1][i]);
        ans += RIP;
        if(num[0][i] > 0 && num[1][i] < 0) num[0][i] -= RIP, num[1][i] += RIP;
        else if(num[0][i] < 0 && num[1][i] > 0) num[0][i] += RIP, num[1][i] -= RIP;
        num[0][i + 1] += num[0][i], num[1][i + 1] += num[1][i];
        if(num[0][i] > 0) ans += num[0][i];
        else ans += -num[0][i];
        if(num[1][i] > 0) ans += num[1][i];
        else ans += -num[1][i];
    }
    printf("%lld\n", ans);
    return 0;
}