ABC 117 | C - Streamline

問題

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

考えたこと

$M <= N$のときはすべてのコマをおいた時点で目的を達成できるので答えは0である。以降は$N < M$として考える。

${X}$はソートしても答えは変わらないのであらかじめソートしておく。以降はソート後の${X_i}$について考える。
${X_i}$の最小値と最大値の間にコマを置くことになる。その際に$N$個のコマは各コマ任意の回数動かせるので以下のようにコマごとに区間ができる。区間が重なるのは移動回数の無駄なので区間が重なることはない。

この時、以下のように$N$個のコマが置かれコマが置かれていない区間は$N-1$個ある。

コマの移動した回数はコマが専有する区間-$N$である。よってコマが置かれていない$N-1$個の区間を最大化すればコマの移動回数が最小化される。

コード

#include <bits/stdc++.h>

#include <atcoder/all>

using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
const int MOD = 1e9 + 7;

int main() {
  ll n, m;
  cin >> n >> m;
  vector<ll> x(m);
  for (int i = 0; i < m; i++) {
    cin >> x[i];
  }
  sort(x.begin(), x.end());
  if (m <= n) {
    cout << 0 << endl;
    return 0;
  }
  // n-1個の区間を長い方から選べばいいい
  vector<int> widths;  // 区間を入れていく
  for (int i = 0; i < m - 1; i++) {
    widths.push_back(abs(x[i + 1] - x[i] - 1));
  }
  int ans = abs(x[m - 1] - x[0] + 1);  // すべてのマス
  sort(widths.rbegin(), widths.rend());
  for (int i = 0; i < n - 1; i++) {  // いらない区間を引く
    ans -= widths[i];
  }
  // マスの数を引く
  ans -= n;
  cout << ans << endl;
}

参考

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