ABC117 C - Streamline

備忘録

問題

atcoder.jp

回答

import sys
import os


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N, M = map(int, sys.stdin.readline().split())
    lines = list(map(int, sys.stdin.readline().split()))
    lines.sort()

    cost = {}
    for i in range(len(lines) - 1):
        tmp = lines[i + 1] - lines[i]
        cost[i] = tmp

    sortedCost = sorted(cost.items(), key=lambda x: x[1], reverse=True)
    ret = 0
    for i, c in sortedCost[N - 1:]:
        ret += c

    print(ret)


if __name__ == '__main__':
    main()

考え方

数直線上の座標をソートして配列にする。
ソートした配列の先頭（もっとも左の座標）から順に、
次の座標との差分（右の座標へ移動するコスト）を算出する。

上記の処理を行うことで、各区間の移動に必要なコスト（コマを動かす回数）が判明するため、
各区間の移動コスト（コマを動かす回数）を高い順にコマを置くことにする。
（置いたコマはその時点で座標に訪れたことになるので、となりの座標から移動するためのコストが不要になる。）

あとは残った座標への移動コストをすべて加算することで答えを求めることができる。

ただし、N個のコマを置いても、最後の1つは移動しなければならないため、
コマを置くことで、不要とすることが出来る移動コストはN-1個であることに注意。