#codefestival2016qualBd. [codefestival_2016_qualB_d]Greedy customers

[codefestival_2016_qualB_d]Greedy customers

nn 个数 a1,a2,,ana_1, a_2, \cdots, a_n。每次操作前自行选择一个正整数 PP

  • a1,a2,,ai1<Pa_1,a_2,\cdots,a_{i-1}< P,且 aiPa_i\ge P,则 aia_i 是特别数,对它进行操作。
  • ai=Pa_i=P,操作不成立。否则(即 ai<Pa_i<P 时),aiaiPa_i\gets a_i-P

问最多可以进行多少次操作。

translated by

https://www.luogu.com.cn/user/367488