求助一道题是否有优秀做法
  • 板块学术版
  • 楼主言琢დ
  • 当前回复31
  • 已保存回复32
  • 发布时间2024/12/18 19:35
  • 上次更新2024/12/18 22:29:27
查看原帖
求助一道题是否有优秀做法
50606
言琢დ楼主2024/12/18 19:35

感觉题目模型看上去很典,但想了下感觉不太会。(没有题目链接,可能确实没做法,所以随便问问)

题目是这样:给定一个数组 {an}\{a_n\},每次:令最小的 一个 aia_i 变成 minji{aj}+1\min\limits_{j\ne i}\{a_j\}+1。这样进行 kk 次操作后,问 mini=1n{ai}\min\limits_{i=1}^{n}\{a_i\} 等于多少。

n3×106n\le3\times10^6k,ai109k,a_i\le10^9

例如:a=[1,2,3]a=[1,2,3],接下来的几次变化依次为:a=[2,3,3]a=[2,3,3]a=[3,3,4]a=[3,3,4]a=[3,4,4]a=[3,4,4]a=[4,4,5]a=[4,4,5],如果此时 k=4k=4,那么输出的结果就是 min{4,4,5}=4\min\{4,4,5\}=4

给定的初始数组是升序输入的,所以想问问有没有线性做法

2024/12/18 19:35
加载中...