AtCoder题解｜Candles

AtCoder题解｜ABC 107C Candles

---

题目信息 📚

【题目描述】

There are $N$ candles placed on a number line. The $i$-th candle from the left is placed on coordinate $x_i$. Here, $x_1 < x_2 < … < x_N$ holds.

Initially, no candles are burning. Snuke decides to light $K$ of the $N$ candles.

Now, he is at coordinate $0$. He can move left and right along the line with speed $1$. He can also light a candle when he is at the same position as the candle, in negligible time.

Find the minimum time required to light $K$ candles.

【输入】

$N$ $K$

$x_1$ $x_2$ $\dots$ $x_N$

【输出】

Print the minimum time required to light $K$ candles.

【数据范围】

• $1 \leq N \leq 10^5$
• $1 \leq K \leq N$
• $x_i$ is an integer.
• $|x_i| \leq 10^8$
• $x_1 < x_2 < … < x_N$

【输入样例1】

5 3
-30 -10 10 20 50

【输出样例1】

40

He should move and light candles as follows:

1. Move from coordinate $0$ to $-10$.
2. Light the second candle from the left.
3. Move from coordinate $-10$ to $10$.
4. Light the third candle from the left.
5. Move from coordinate $10$ to $20$.
6. Light the fourth candle from the left.

【输入样例2】

3 2
10 20 30

【输出样例2】

20

【输入样例3】

1 1
0

【输出样例3】

0

• There may be a candle placed at coordinate $0$.

【输入样例4】

8 5
-9 -7 -4 -3 1 2 3 4

【输出样例4】

10

【题目来源】

https://atcoder.jp/contests/abc107/tasks/arc101_a

---

题目解析 🍉

【题目分析】

贪心。

选择的K个点一定是相邻的K个点。

枚举比较所有 「相邻点组成的区间长度 + 起点到端点的最小距离」即可。

贪心策略灵感来源以下两题：

https://atcoder.jp/contests/abc117/tasks/abc117_c

https://atcoder.jp/contests/abc115/tasks/abc115_c

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL x[N], ans, k, n, cur;

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    // 读入坐标点
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> x[i];

    // 贪心
    ans = LLONG_MAX;
    for (int i = 1; i + k - 1 <= n; i++) {
        cur = x[i + k - 1] - x[i] + min(abs(x[i] - 0), abs(x[i + k - 1] - 0));
        ans = min(cur, ans);
    }

    cout << ans << endl;
    return 0;
}