👌

ABC 117 | C - Streamline

1 min read

問題

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;
}

参考

Discussion

ログインするとコメントできます