题目大意

在一个购物APP中，有一个核心购物系统，该系统的接口被多个客户端调用。每个客户端有不同的请求数量，系统能接受的最大调用量是一个给定的值。要求设定一个阈值 value，如果某个客户端的请求量超过该阈值，则将其请求数量限制为这个阈值。我们的目标是求出最大的 value 值，确保所有客户端的请求总量不会超过核心购物系统的最大调用量。

思路

二分答案

要求在保证客户端请求的数量不会超过核心购物系统的最大调用量的情况下，使得阈值 $value$ 尽可能大。一般该类问题可以尝试使用二分答案加验证答案正确性的方法尝试求解。

使用二分答案的方法，一般要考虑两个因素：

1. 二分值(本题中为阈值$value$)的变化，对模型整体的评估(本题中为$\sum_{1\le{i}\le{n}}{R_i}$)是具有单调性的
2. 当确定二分值时，我们会借助该二分值去计算模型整体的评估值，该计算方法应该具有让人可以接收的复杂度

单调性

本题中的单调性依据题意应当是显而易见的：

1. 当阈值 $value$ 变小时，更多的客户端发起的请求量会被限制，因此总的请求量就会减小
2. 当阈值 $value$ 变大时，更少的客户端发起的请求量会被限制，许多客户端都能满足其发起的所有请求，于是总的请求量就会变大.

所以，答案随着阈值单调递增 ， 可以使用二分答案！

答案验证

当获得了阈值 $value$ 后，依据题意验证答案的时间复杂度是 $O(N)$，其与二分答案所带来的时间复杂度叠加后，总的时间复杂度为 $O(NlogN)$(二分答案引入的时间复杂度应当是 $O(log(max(R_i)))$，但是$R_i$的最大范围与$N$的范围是相同的，所以时间复杂度可以简化为该结果)，这是该题能够接收的时间复杂度，因此二分答案的做法是可行的。

代码说明

整体代码流程

1.输入读取：

读取所有客户端的请求量，并存储在数组中。 读取最大调用量 th，作为验证的上限。

2.初步检查：

计算所有请求量的总和，如果总和小于等于最大调用量 th，直接输出 -1，表示不存在有效的阈值。

3.二分查找：

定义查找的区间，初始左边界为 -1，右边界为 100001。 进行二分查找，在每次迭代中计算中间值 mid 并使用 check 函数验证其合法性。 如果 check(mid) 返回 true，更新左边界为 mid，否则更新右边界。

4.输出结果：

最终输出 l，表示在满足条件下能达到的最大阈值。

时间复杂度：$O(NlogN)$

代码

CPP

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

#define ll long long // 定义 ll 为 long long 类型

ll a[100010], n; // 数组 a 用于存储请求量，n 为请求数量
ll th; // 最大调用量

// 验证当前阈值 value 的有效性
bool check(ll value) {
    ll sum = 0; // 初始化总和
    for (int i = 1; i <= n; ++i) {
        if (a[i] <= value) 
            sum += a[i]; // 如果请求量未超出阈值，累加实际请求量
        else 
            sum += value; // 如果请求量超出阈值，累加阈值
    }
    return sum <= th; // 返回总和是否在最大调用量以内
}

int main() {
    // freopen("test.in","r",stdin); // 可选：用于调试时从文件读取输入

    ll sum = 0; // 用于计算总请求量
    n++; // 从 1 开始计数
    // 读取数据直到 EOF
    while (scanf("%lld", &a[n]) != EOF) {
        ++n; // 增加请求数量
    }
    n--; // 调整 n 的值
    th = a[n]; // 最后一个输入值作为最大调用量
    n--; // 调整 n 的值
    for (int i = 1; i <= n; ++i) 
        sum += a[i]; // 计算所有请求的总和

    // 检查如果总请求量不超过最大调用量，输出 -1
    if (sum <= th) {
        puts("-1");
        return 0;
    }

    // 二分答案，采用开区间的二分方式
    int l = -1, r = 100001, mid; // 初始化二分查找的边界
    while (l + 1 < r) {
        mid = (l + r) >> 1; // 计算中间值
        if (check(mid)) 
            l = mid; // 如果当前 mid 合法，更新左边界
        else 
            r = mid; // 否则更新右边界
    }
    
    // check 函数能够保证 mid 的值是合法的，因此最终 l 即为答案
    printf("%lld\n", l); // 输出结果，l 为最大合法阈值
    return 0; // 程序结束
}

python

# 定义一个足够大的数组来存储请求量
a = [0] * 100010
n = 0  # 请求数量
th = 0  # 最大调用量

# 验证当前阈值 value 的有效性
def check(value):
    sum_val = 0  # 初始化总和
    for i in range(1, n + 1):  # 遍历所有请求
        if a[i] <= value:
            sum_val += a[i]  # 如果请求量未超出阈值，累加实际请求量
        else:
            sum_val += value  # 如果请求量超出阈值，累加阈值
    return sum_val <= th  # 返回总和是否在最大调用量以内

if __name__ == "__main__":
    sum_val = 0  # 用于计算请求量的总和
    n += 1  # 从 1 开始计数

    # 读取数据
    while True:
        try:
            a[n] = int(input())  # 读取请求量
            n += 1  # 增加请求数量
        except EOFError:  # 处理 EOF
            break  # 退出循环
    n -= 1  # 调整 n 的值
    th = a[n]  # 将最后一个输入值作为最大调用量
    n -= 1  # 调整 n 的值

    # 计算所有请求的总和
    for i in range(1, n + 1):
        sum_val += a[i]

    # 检查如果总请求量不超过最大调用量，输出 -1
    if sum_val <= th:
        print("-1")  # 输出 -1
        exit(0)  # 退出程序

    # 二分答案，采用开区间的二分方式
    l = -1  # 左边界
    r = 100001  # 右边界
    while l + 1 < r:
        mid = (l + r) // 2  # 计算中间值
        if check(mid):  # 如果当前 mid 合法
            l = mid  # 更新左边界
        else:
            r = mid  # 更新右边界

    # check 函数能够保证 mid 的值是合法的，因此最终 l 即为答案
    print(l)  # 输出结果

Java

import java.util.Scanner;

public class Main {
    static long[] a; // 存储请求量
    static int n; // 请求数量
    static long th; // 最大调用量

    // 验证当前阈值 value 的有效性
    static boolean check(long value) {
        long sum = 0; // 初始化总和
        for (int i = 1; i <= n; ++i) { // 遍历所有请求
            if (a[i] <= value) 
                sum += a[i]; // 如果请求量未超出阈值，累加实际请求量
            else 
                sum += value; // 如果请求量超出阈值，累加阈值
        }
        return sum <= th; // 返回总和是否在最大调用量以内
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建扫描器以读取输入
        a = new long[100010]; // 初始化请求量数组
        n = 0; // 请求数量初始化

        // 读取数据直到输入结束
        while (scanner.hasNext()) {
            a[++n] = scanner.nextLong(); // 将输入的请求量存入数组
        }
        th = a[n]; // 将最后一个输入值作为最大调用量
        long sum = 0; // 初始化请求量总和

        // 计算所有请求的总和
        for (int i = 1; i < n; ++i) 
            sum += a[i];

        // 检查如果总请求量不超过最大调用量，输出 -1
        if (sum <= th) {
            System.out.println("-1"); // 输出 -1
            return; // 结束程序
        }

        // 二分答案，采用开区间的二分方式 
        int l = -1, r = 100001, mid; // 初始化二分查找的边界
        while (l + 1 < r) {
            mid = (l + r) >> 1; // 计算中间值
            if (check(mid)) // 如果当前 mid 合法
                l = mid; // 更新左边界
            else
                r = mid; // 否则更新右边界
        }
        
        // check 函数能够保证 mid 的值是合法的，因此最终 l 即为答案
        System.out.println(l); // 输出结果
    }
}

Go

package main

import (
	"fmt"
)

// 定义变量
var a []int64 // 存储请求量
var n int     // 请求数量
var th int64  // 最大调用量

// 验证当前阈值 value 的有效性
func check(value int64) bool {
	sum := int64(0) // 初始化总和
	for i := 1; i <= n; i++ { // 遍历所有请求
		if a[i] <= value {
			sum += a[i] // 如果请求量未超出阈值，累加实际请求量
		} else {
			sum += value // 如果请求量超出阈值，累加阈值
		}
	}
	return sum <= th // 返回总和是否在最大调用量以内
}

func main() {
	var num int64
	// 读取数据
	for {
		_, err := fmt.Scanf("%d", &num) // 读取请求量
		if err != nil { // 处理 EOF
			break
		}
		a = append(a, num) // 将输入的请求量添加到数组中
	}
	n = len(a) - 2 // 设置请求数量（排除最后两个元素）
	th = a[n+1]    // 将最后一个输入值作为最大调用量
	sum := int64(0) // 初始化请求量总和

	// 计算所有请求的总和
	for i := 1; i <= n; i++ {
		sum += a[i]
	}

	// 检查如果总请求量不超过最大调用量，输出 -1
	if sum <= th {
		fmt.Println("-1") // 输出 -1
		return // 结束程序
	}

	// 二分答案，采用开区间的二分方式 
	l, r := -1, 100001 // 初始化二分查找的边界
	for l+1 < r { // 当 l + 1 < r 时继续查找
		mid := (l + r) / 2 // 计算中间值
		if check(int64(mid)) { // 如果当前 mid 合法
			l = mid // 更新左边界
		} else {
			r = mid // 否则更新右边界
		}
	}
	
	// check 函数能够保证 mid 的值是合法的，因此最终 l 即为答案 
	fmt.Println(l) // 输出结果
}

Js

const readline = require('readline'); // 引入 readline 模块，用于处理输入

// 验证当前阈值 value 的有效性
function check(value) {
    let sum = 0; // 初始化总和
    for (let i = 1; i <= n; i++) { // 遍历所有请求
        if (a[i] <= value) 
            sum += a[i]; // 如果请求量未超出阈值，累加实际请求量
        else 
            sum += value; // 如果请求量超出阈值，累加阈值
    }
    return sum <= th; // 返回总和是否在最大调用量以内
}

function main() {
    const rl = readline.createInterface({
        input: process.stdin, // 设置输入流
        output: process.stdout // 设置输出流
    });

    let a = []; // 用于存储请求量
    let n = 0; // 请求数量
    let th = 0; // 最大调用量

    // 读取数据
    rl.on('line', (line) => {
        a.push(parseInt(line)); // 将输入的请求量转换为整数并存入数组
        n++; // 请求数量加一
    });

    rl.on('close', () => {
        n -= 2; // 调整请求数量（排除最后两个元素）
        th = a[n + 1]; // 将最后一个输入值作为最大调用量
        let sum = 0; // 初始化请求量总和
        
        // 计算所有请求的总和
        for (let i = 1; i <= n; i++)
            sum += a[i];

        // 检查如果总请求量不超过最大调用量，输出 -1
        if (sum <= th) {
            console.log("-1"); // 输出 -1
            return; // 结束程序
        }

        // 二分答案，采用开区间的二分方式
        let l = -1, r = 100001, mid; // 初始化二分查找的边界
        while (l + 1 < r) { // 当 l + 1 < r 时继续查找
            mid = Math.floor((l + r) / 2); // 计算中间值
            if (check(mid)) // 如果当前 mid 合法
                l = mid; // 更新左边界
            else
                r = mid; // 否则更新右边界
        }
        
        // check 函数能够保证 mid 的值是合法的，因此最终 l 即为答案
        console.log(l); // 输出结果
    });
}

main(); // 调用主程序

题目内容

在一个购物APP中，有一个核心购物系统，它的接口被 $N$ 个客户端调用。这些客户端负责处理来自不同渠道的交易请求，并将这些请求发送给核心购物系统。每个客户端有不同的调用量 $R=[R_1,R_2,...,R_N]$，表示在一定时间内，这个客户端向核心购物系统发送的交易请求的数量。核心购物系统必须能够及时响应所有的请求，以确保交易顺利进行。

然而，最近核心购物系统出现了集群故障，导致交易请求的处理速度变慢。为了避免系统崩溃，必须临时降级并限制调用量。具体而言，核心购物系统能接受的最大调用量为 $cnt$，如果客户端发送的请求总量超过 $cnt$，则必须限制一些系统的请求数量，以确保核心购物系统不会超负荷工作。

现在需要一个降级规则，来限制客户端的请求数量。规则如下：

• 如果 $sum(R_1,R_2,...,R_N)$ 小于等于 $cnt$ ，则全部可以正常调用，返回 $-1$；
• 如果 $sum(R_1,R_2,...,R_N)$ 大于 $cnt$，则必须设定一个阈值 $value$，如果某个客户端发起的调用量超过 $value$，则该客户端的请求数量必须限制为 $value$。其余未达到 $value$ 的系统可以正常发起调用。要求求出最大的 $value$（$value$ 可以为0）。

为了保证交易的顺利进行，必须保证客户端请求的数量不会超过核心购物系统的最大调用量，同时最大的 $value$ 要尽可能的大。需要高效地解决这个问题，以确保购物系统的高效性。

输入描述

第一行：每个客户端的调用量(整型数组)

第二行：核心购物系统的最大调用量

$0 < R.length\le 10^5$ ， $0\le R[i]\le 10^5$ ， $0\le cnt \le 10^9$

输出描述

调用量的阈值 $value$

样例

样例一

输入

1 4 2 5 5 1 6 
13

输出

2

样例解释

因为 $1+4+2+5+5+1+6>13$ ，将 $value$ 设置为 $2$ ，则 $1+2+2+2+2+1+2=12<13$ 。所以 $value$ 为 $2$ 。

样例二

输入

1 7 8 8 1 0 2 4 9
7

输出

0

样例解释

因为即使 $value$ 设置为 $1$ , $1+1+1+1+1+1+1+1=8>7$ 也不满足，所以 $value$ 只能为 $0$ 。