思路

容易发现一种正确的贪心策略：不断的对数组的最大值进行减一操作，直到它的前 k 大的数之和小于等于 s。 考虑二分查找第一次数组的前 k 大的数之和小于等于 s 时，数组的最大值 mid，显然数组内大于 mid 的值都需要被操作到小于等于 mid。 设当前操作后数组内有 cnt 个 mid，同时数组的前 k 大数的和为 sum，容易发现当 sum <= s 时，可以直接返回当前操作数，否则我们需要把一些值为 mid 的数减少 1 直到 sum <= s。 接下来，我们讨论操作一次值为 mid 的数会发生什么: 当 cnt > k 时，容易发现操作后实际上还有 k 个值为 mid 的数，前 k 大和不发生改变。 否则当 cnt <= k 时，值为 mid 的数显然在前 k 大里面，同时将它减一后也没有多余的值为 mid 的数能换上去，因此前 k 大和减一 特别地，当 cnt <= 1 时，返回当前中点无解，否则返回当前操作数作为答案即可。

代码

python使用pypy提交

题目内容

小红有一个长度为$n$的数组$a$，其$a_i=i$，下标从$1$开始。每次操作可以令$a_i=a_i-1$，问：至少需要操作几次使得排列中不存在任意$k$个元素和大于$sum$。

输入描述

第一行一个整数$t$($1≤t≤10$)，表示询问个数。

接下来$t$行，每行三个整数

$n\ k\ sum$($1≤k≤n≤10^6,1≤sum≤10^9$)

$\sum n≤10^6$

输出描述

每个询问输出一行，表示最少操作次数

样例1

输入

2
5 2 8
6 3 8

输出

1
8

说明

[$1,2,3,4,5$]修改$1$次得到[$1,2,3,4,4$],满足要求。

[$1,2,3,4,5,6$]修改8次得到[$1,2,2,2,3,3$]满足要求。