对于这种答案需要求 最大/最小值 的问题,如果不知道怎么下手,并且题目是有区间性质的时候,可以尝试使用二分答案。
可以发现对于当前帖子,要让当前帖子的点赞数最快的达到最大值,一定是当前帖子点一下,然后找到其他帖子(点赞数最小的那个)点一下,重复这个操作即可。
小红每次查看他的题解数据,发现都会有一篇题解的赞数+1,并且之后赞数增加的,必是另一篇题解。
小红想知道,当某一篇题解赞数最多时,所有题解赞数和的最小值是多少?
输入包含2行。
第一行两个正整数n(1≤n≤105),表示小红的题解的数量
第二行n个正整数ai(1≤ai≤109),表示小红每个笔记的点赞数。
输出n行,每行输出一个整数,代表第i个笔记变成所有笔记赞数最多时,此时所有的笔记赞数之和的最小值。
特殊的,如果第i个笔记永远无法变成赞数最多,则输出-1.
输入
3
3 1 4
输出
9
15
8