AtCoder题解|ABC 117C Streamline
题目信息 📚
【题目描述】
We will play a one-player game using a number line and $N$ pieces.
First, we place each of these pieces at some integer coordinate. Note that multiple pieces can be placed at the same coordinate.
Our objective is to visit all of the $M$ coordinates $X_1, X_2, \ldots, X_M$ with these pieces, by repeating the following move:
Move: Choose a piece and let $x$ be its coordinate. Put that piece at coordinate $x+1$ or $x-1$.
The coordinates where we initially place the pieces are already regarded as visited.
Find the minimum number of moves required to achieve the objective.
【输入】
The input is given from Standard Input in the following format:
$N$ $M$
$X_1$ $X_2$ $\ldots$ $X_m$
【输出】
Find the minimum number of moves required to achieve the objective.
【数据范围】
All values in the input are integers.
- $1 \leq N \leq 10^5$
- $1 \leq M \leq 10^5$
- $-10^5 \leq X_i \leq 10^5$
- $X_1, X_2, \ldots, X_M$ are all different.
【输入样例1】
2 5
10 12 1 2 14
【输出样例1】
5
The objective can be achieved in five moves as follows, and this is the minimum number of moves required:
- Initially, put the two pieces at coordinates $1$ and $10$.
- Move the piece at coordinate $1$ to $2$.
- Move the piece at coordinate $10$ to $11$.
- Move the piece at coordinate $11$ to $12$.
- Move the piece at coordinate $12$ to $13$.
- Move the piece at coordinate $13$ to $14$.
【输入样例2】
3 7
-10 -3 0 9 -100 2 17
【输出样例2】
19
【输入样例3】
100 1
-100000
【输出样例3】
0
【题目来源】
https://atcoder.jp/contests/abc117/tasks/abc117_c
题目解析 🍉
【题目分析】
思维 + 贪心。
首先对所有坐标点,从小到大排序。(这步很容易想到)
分类讨论:
$n >= m$ 时,所有坐标点上均有 piece(棋子),无需移动,答案为 $0$。
问题关键在于 $n < m$ 时分配如何 pieces。
- 当只有一个 piece 时,我们只需要将这个 piece 放在整个区间的左端点,然后不断移动 piece 至区间右端点,就可以得到最优答案(这样操作避免了来回移动造成的重复)。
- 当有多个 pieces 时
- 先以 2个 pieces 为例,我们容易想到把这两个 pieces 放到距离最大的 interval 的两个端点 $[a, b]$,然后一个向左移动,一个向右移动,这样就可以跳过最大的interval。(但实际上,我们完全可以把左边的 piece 放到左端点,再移动到端点 $a$,也能实现同样的效果)
- 假设有 3个 pieces 时,我们只需要找到距离次大的 interval 的两个端点 $[c, d]$,在之前的基础上,把第 3个 piece 放到 $d$ 上即可。
- …
- 当有 $n$个 pieces 时,我们将所有 intervals 排序从大到小排序(共有 $m-1$ 个),跳过前 $n-1$ 个距离大的 intervals,剩下 $(m-1) - (n-1) = m - n$ 个 intervals 的和即为答案。
【C++代码】
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, m, x[N];
int main() {
ios::sync_with_stdio(false); //cin读入优化
cin.tie(0);
// 读入数据,并且对坐标点排序
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> x[i];
sort(x + 1, x + m + 1);
// n >= m时,所有坐标点上都可以至少有一个piece,无需移动
if (n >= m) {
cout << 0 << endl;
return 0;
}
// 由m个坐标点,读入m-1个intervals
vector<int> intervals;
for (int i = 1; i <= m - 1; i++) {
intervals.push_back(x[i + 1] - x[i]);
}
// intervals从大到小排序
sort(intervals.rbegin(), intervals.rend());
// 计算剩余 intervals 总和
int sum = 0;
for (int i = n - 1; i < intervals.size(); i++) {
sum += intervals[i];
}
cout << sum << endl;
return 0;
}