[Codeforces] Codeforces Round #573 (Div. 2) C. Tokitsukaze and Discard Items

2019年7月13日2020年9月8日

問題

方針

題意

\( 1 \) から \( n \) までの数字があり、\( k \) 個ごとに仕切りがあります。初期の配置では、仕切り \( i \) には、\( ik \) から \((i + 1)k\) までの数字が存在しています。

ここで、\( p_i \) の数字を次の手順で消していきます。仕切りを小さい方から調べていき、\( p_i \) が含まれる仕切り \( j \) とすると、\( j \) に含まれる数字の最大値まで、\( p_{i} \) 以降の数字を一度に消すことができます。また、数字を消した後、後ろの前に詰めていきます。これらを全ての \( p_i \) について行います。

仕切りに含まれる最大値を考える

仕切りに含まれる最大値を \( r \) とします。一番最初のページの仕切りは、\( r_1 = k \) となりますが、\( k < p_1 \) のとき、

\[p_1 \leq km\]

を満たす最小の \( m \) を \( m^{*} \) とすると、\( r_1 = km^{*} \) となります。

次に、\( r_1 \) 以下の \( p_i\) の個数を数えます。このとき、\( r_1 \) 以下の \( p_i \) は一回の操作で消すことができます。この個数を \( t_1 \) とし、\( r < p_j \) のとき、操作回数が \( 1 \) 増加し、\( r_2 = r_1 + t_1 \) とします。また、このとき、\( r_2 < p_j \) のとき、

\[r_2 \gets \lceil \dfrac{p_j – r_2}{k} \rceil k + r_2\]

と更新します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int m;
  ll n, k;
  cin >> n >> m >> k;
  ll p[m];
  for (int i = 0; i < m; i++) {
    cin >> p[i];
  }
  ll r = k;
  if (r < p[0]) {
    r = (p[0] - r + k - 1) / k * k + r;
  }
  ll cnt = 1;
  ll t = 0;
  for (int i = 0; i < m; i++) {
    if (p[i] <= r) {
      t++;
    } else {
      r += t;
      if (r < p[i]) {
        r = ((p[i] - r + k - 1) / k) * k + r; 
      }
      t = 1;
      cnt++;
    }
  }
  cout << cnt << "\n";
  return 0;
}