思路

容易发现一种正确的贪心策略：不断的对数组的最大值进行减一操作，直到它的前 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 时，返回当前中点无解，否则返回当前操作数作为答案即可。

代码

def check(n, k, s, mid):
    # cost记录总操作次数
    cost = 0
    
    # 计算出所有元素变为mid时的操作次数
    # 从1到n，每个元素需要减少到mid，操作次数为max(0, i - mid)
    for i in range(1, n + 1):
        cost += max(0, i - mid)
    
    # cnt表示数组中大于mid的元素个数
    cnt = n - mid + 1
    
    # sum表示从数组的最后k个元素的和
    total_sum = 0
    for i in range(n - k + 1, n + 1):
        total_sum += min(i, mid)
    
    # 当sum大于给定的s并且有剩余元素可调整时，进行调整，即将部分的mid转为mid-1
    while total_sum > s and cnt > 1:
        if cnt > k:
            cnt -= 1  # 如果剩余的元素数大于k，减少cnt，不影响sum
        else:
            cnt -= 1  # 否则减少一个元素，并且减少总和
            total_sum -= 1
        cost += 1  # 每次减少，操作数加1
    
    # 如果调整后sum仍然大于s，返回-1，表示不合法
    if total_sum > s:
        return -1
    return cost  # 返回最少操作次数


def main():
    # 输入测试用例的数量
    t = int(input())
    
    for _ in range(t):
        # 输入每个用例的n, k, s
        n, k, s = map(int, input().split())
        
        # 初始化二分查找的左右边界
        left, right = 0, n
        ans = -1  # ans用来记录找到的合法的mid
        
        # 使用二分查找来确定mid
        while left <= right:
            mid = left + (right - left) // 2  # 取中间值mid
            if check(n, k, s, mid) != -1:  # 检查mid是否合法
                ans = mid  # 如果合法，记录当前mid
                left = mid + 1  # 尝试找更大的mid
            else:
                right = mid - 1  # 否则缩小范围
        
        # 输出最终找到的合法mid对应的最小操作次数
        print(check(n, k, s, ans))

# 程序入口
if __name__ == "__main__":
    main()

#include <iostream>
#include <algorithm>
using namespace std;

int check(int n, int k, int s, int mid) {
    // cost记录总操作次数
    int cost = 0;

    // 计算出所有元素变为mid时的操作次数
    // 从1到n，每个元素需要减少到mid，操作次数为max(0, i - mid)
    for (int i = 1; i <= n; i++) {
        cost += max(0, i - mid);
    }

    // cnt表示数组中大于mid的元素个数
    int cnt = n - mid + 1;

    // sum表示从数组的最后k个元素的和
    int total_sum = 0;
    for (int i = n - k + 1; i <= n; i++) {
        total_sum += min(i, mid);
    }

    // 当sum大于给定的s并且有剩余元素可调整时，进行调整
    while (total_sum > s && cnt > 1) {
        if (cnt > k) {
            cnt--;  // 如果剩余的元素数大于k，减少cnt，不影响sum
        } else {
            cnt--;  // 否则减少一个元素，并且减少总和
            total_sum--;
        }
        cost++;  // 每次减少，操作数加1
    }

    // 如果调整后sum仍然大于s，返回-1，表示不合法
    if (total_sum > s) {
        return -1;
    }
    return cost;  // 返回最少操作次数
}

int main() {
    int t;
    // 输入测试用例的数量
    cin >> t;

    while (t--) {
        // 输入每个用例的n, k, s
        int n, k, s;
        cin >> n >> k >> s;

        // 初始化二分查找的左右边界
        int left = 0, right = n;
        int ans = -1;  // ans用来记录找到的合法的mid

        // 使用二分查找来确定mid
        while (left <= right) {
            int mid = left + (right - left) / 2;  // 取中间值mid
            if (check(n, k, s, mid) != -1) {  // 检查mid是否合法
                ans = mid;  // 如果合法，记录当前mid
                left = mid + 1;  // 尝试找更大的mid
            } else {
                right = mid - 1;  // 否则缩小范围
            }
        }

        // 输出最终找到的合法mid对应的最小操作次数
        cout << check(n, k, s, ans) << endl;
    }

    return 0;
}

import java.util.Scanner;

public class Main {

    public static int check(int n, int k, int s, int mid) {
        // cost记录总操作次数
        int cost = 0;

        // 计算出所有元素变为mid时的操作次数
        // 从1到n，每个元素需要减少到mid，操作次数为max(0, i - mid)
        for (int i = 1; i <= n; i++) {
            cost += Math.max(0, i - mid);
        }

        // cnt表示数组中大于mid的元素个数
        int cnt = n - mid + 1;

        // sum表示从数组的最后k个元素的和
        int total_sum = 0;
        for (int i = n - k + 1; i <= n; i++) {
            total_sum += Math.min(i, mid);
        }

        // 当sum大于给定的s并且有剩余元素可调整时，进行调整
        while (total_sum > s && cnt > 1) {
            if (cnt > k) {
                cnt--;  // 如果剩余的元素数大于k，减少cnt，不影响sum
            } else {
                cnt--;  // 否则减少一个元素，并且减少总和
                total_sum--;
            }
            cost++;  // 每次减少，操作数加1
        }

        // 如果调整后sum仍然大于s，返回-1，表示不合法
        if (total_sum > s) {
            return -1;
        }
        return cost;  // 返回最少操作次数
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 输入测试用例的数量
        int t = scanner.nextInt();

        while (t-- > 0) {
            // 输入每个用例的n, k, s
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            int s = scanner.nextInt();

            // 初始化二分查找的左右边界
            int left = 0, right = n;
            int ans = -1;  // ans用来记录找到的合法的mid

            // 使用二分查找来确定mid
            while (left <= right) {
                int mid = left + (right - left) / 2;  // 取中间值mid
                if (check(n, k, s, mid) != -1) {  // 检查mid是否合法
                    ans = mid;  // 如果合法，记录当前mid
                    left = mid + 1;  // 尝试找更大的mid
                } else {
                    right = mid - 1;  // 否则缩小范围
                }
            }

            // 输出最终找到的合法mid对应的最小操作次数
            System.out.println(check(n, k, s, ans));
        }
        
        scanner.close();
    }
}

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$]满足要求。