Edited at

ABC117 C - Streamline(300点)


問題概要

問題へのリンク

数直線上に座標 $X_1,X_2,...,X_M$ の $M$ 個の地点がある。$N$個のこまを使って、以下の操作を行う。

移動 : コマを $1$ つ選び、そのコマの座標を $x$ とする。そのコマを座標 $x+1$ もしくは座標 $x−1$ に移動する。

$M$個の地点を全て訪れるように移動する時、最小の移動回数を求めよ。

なお最初にコマを置いた座標はその時点で訪れたことにする。


制約条件


  • 入力はすべて整数である。

  • $1≤N≤10^5$

  • $1≤M≤10^5$

  • $−10^5≤X_i≤10^5$

  • $X_1,X_2,...,X_M$ は全て異なる。


考えたこと

任意の二点間の差が移動距離となる。コマが複数個ある場合、当然移動距離が長い部分は移動したくない。

例えば入力例1だと移動距離は以下の図のようになる。


入力例1

2 5

10 12 1 2 14


image.png

このときコマが二つあるので、移動距離が最も大きい2と10の間は移動するコマを変えることでショートカットできる。そうすれば移動回数は最小となる。

よって移動距離が長い二点間の移動は移動させるコマを変えることでショートカットする。

ショートカットできる回数はコマ数$-1$ つまり $N-1$ となる。

なので、二点間の差をとって配列につめていき、大きい数から$N-1$個消していけばよい。

「コマ数が地点の数より少ない」と「地点が一つしかない」ケースを想定すると少し実装がめんどうだが、そこまで難しくないのでわからなければ以下のコードを参考にしてほしい。


解答


c.cs

using System;

using System.Collections.Generic;
using System.Linq;

class Program
{
static void Main(string[] args) {
int[] s = Console.ReadLine().Split().Select(int.Parse).ToArray();
List<int> x = Console.ReadLine().Split().Select(int.Parse).ToList();
x.Add(x.Min());
x.Sort();
Console.WriteLine(solve(s[0], s[1], x));
}
static int solve(int n, int m, List<int> x) {
int[] l = new int[m];
for(int i = 0; i < m; i ++) {
l[i] = Math.Abs(x[i+1]-x[i]);
}
Array.Sort(l);
Array.Reverse(l);
for(int i = 0; i < n-1; i ++) {
l[i] = 0;
if(i == m-1) break;
}
return l.Sum();
}
}