CF1118D2 Coffee and Coursework (Hard Version)(二分)

题目描述

Input

The first line of the input contains two integers n and m (1≤n≤2⋅105, 1≤m≤109) — the number of cups of coffee and the number of pages in the coursework.

The second line of the input contains n integers a1,a2,…,an (1≤ai≤109), where ai is the caffeine dosage of coffee in the i-th cup.

Output If it is impossible to write the coursework, print -1. Otherwise print the minimum number of days Polycarp needs to do it.

Examples input

5 8 2 3 1 1 2

output

4

input

7 10 1 3 4 2 1 4 2

output

2

input

5 15 5 5 5 5 5

output

1

input

5 16 5 5 5 5 5

output

2

input

5 26 5 5 5 5 5

output

-1

题目大意: 有n杯咖啡,要做m份作业,每杯咖啡有一个值a,表示喝完能做的作业数量,但是如果一天之内喝了超过一杯,那么每喝一杯就会少做k-1件作业(即第一杯为ai,第二杯为max(0,ai-1),第n杯为max(0,ai-n)),问最少多少天能做完作业

解题思路: 要使咖啡收益最大化,那么就得使值大的在每天作为第一杯咖啡使用,那么可以二分答案,每次取一个天数mid,跑for遍历咖啡,每mid杯咖啡后更新减的值(每天一杯,那么每mid天之后的就是要减去值的),最后输出最少的天数即可,如果咖啡的值加起来也无法超过作业的数量的话,那么显然是无法完成的,输出-1即可

题外话: python的效率是比较慢的,在打acm过程中是很吃亏的,如果oj有pypy选项的,建议使用pypy提交,pypy虽然库支持比较少,但是运行效率会比python快很多

代码如下:

class Solution(): def __init__(self): firstline=input().split() n=int(firstline[0]) m=int(firstline[1]) a=input().split() for i in range(n): a[i]=int(a[i]) a.sort(key=int,reverse=True)#快排,让值高的咖啡在前面 l=1 r=m+1 while l<r: mid=int(l+r>>1) sum=0 for i in range(n): if a[i]-int(i/mid)<=0:#剪枝,无法获得值了就没必要再运算了 break sum+=max(0,a[i]-int(i/mid))#第一个mid范围表示每天的第一杯,第二个mid范围表示第二杯,即要减去的值是i/mid if sum>=m: #同理,做完了作业就不需要再喝咖啡了 break if sum>=m: r=mid else: l=mid+1 if r==m+1: print('-1') else: print(r) if __name__ == '__main__': Solution()