ABC318 C - Blue Spring

■考えたこと

問題文を読んでも解法が思いつかなかった。

とりあえず入力例1で周遊パスを買っていったときの様子を紙に書いてみた。

1日周遊パスは2枚セットで10円で販売されているので各セット購入したとすると

・0セット：7 + 1 + 6 + 3 + 6 = 23円

・1セット：(10 x 1) + (0 + 1 + 0 + 3 + 6) = 20円 ← 料金が高い日順に周遊パスを割り当て

・2セット：(10 x 2) + (0 + 1 + 0 + 0 + 0) = 21円

・3セット：(10 x 3) + (0 + 0 + 0 + 0 + 0) = 30円

となる。

ここまで書き出すと3セット以降は料金が高くなっていくだけなので

試す必要がないことが分かった。

つまり5日間すべてを周遊パスで割り当てするためには3セットで十分。

これは N / D の切り上げ (以降k) で計算できる。 

制約的にkセット試せば間に合うと推測。

後はkセット購入した場合の合計料金をどう計算するかだが、下記を書いて

累積和でいけそうと推測。

f : 1   3   6     6    7

s : 0   1   4   10  16  23

以下はACしたコード。

using ll = long long;

int main() {
  int n, d, p;
  cin >> n >> d >> p;
  vector f(n);
  for (int i = 0; i < n; i++) cin >> f[i];
  sort(f.begin(), f.end());

  vector s(n + 1);
  for (int i = 0; i < n; i++) {
    s[i + 1] = s[i] + f[i];
  }

  int sd = (n + d - 1) / d;
  
  const ll INF = 1e18;
  ll ans = INF;
  for (ll i = 0; i <= sd; i++) {
    ll sum = 0;
    if (n - i * d > 0) sum += s[n - i * d];
    sum += p * i;
    ans = min(ans, sum);
  }
  cout << ans << endl;
}