atcoder#ARC069C. [ARC069E] Frequency
[ARC069E] Frequency
题目描述
すぬけくんは数列を作るのが好きです。
から までの番号がついた石の山があります。 番の石の山は 個の石からなります。
すぬけくんは以下の手順により長さ の数列 を構成することにしました。
- 石の数が最大である山のうち、最も番号が小さい山の番号を として、 の末尾に を追加する
- 石が 個以上存在する山を つ選んで、選んだ山から石を つ取り除く
- 石が 個以上存在する山が存在するなら へ、そうでなければ数列の構成を終了する
が辞書順で最小の数列となるようにしたとき、 に という数がそれぞれいくつ含まれるか求めなさい。
输入格式
入力は以下の形式で標準入力から与えられる。
输出格式
答えを 行に出力せよ。 行目では辞書順で最小の における の出現回数を出力せよ。
题目大意
给定 堆石子,第 堆大小为 。
现在你需要构造一个长度 的序列 ,构造流程如下:
-
找到当前石子数量最多的那堆石子,如果有多个则取最前面哪个,将下标记作 ,将 写在 末尾。
-
选择一堆石子,拿一个石子出来。
-
如果还有石子剩余,重复这个流程。
现在需要你最小化 的字典序,输出 在 中出现了多少次。
2
1 2
2
1
10
1 2 1 3 2 4 2 5 8 1
10
7
0
4
0
3
0
2
3
0
提示
制約
Sample Explanation 1
以下の手順で辞書順最小であるような数列が構成できます。 - 石の数が最大であるような山は 番なので を に追加する。その後、番号 の山から石を つ取り除く。 - 石の数が最大であるような山は 番と 番なので、最も番号が小さい を に追加する。その後、番号 の山から石を つ取り除く。 - 石の数が最大であるような山は 番なので を に追加する。その後、番号 の山から石を つ取り除く。 このときできる数列は となります。 は つ含まれ、 は つ含まれます。