二分答案

1.化简题意

给你一个数组$R$，寻找一个最大的阈值$v$，满足条件$T:\sum min(R_i,v) \leq cnt$

2.观察性质

本题为2023年4月12日华为暑期实习机考原题

华为机考的介绍点击这里

题目内容

在一个购物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$ 。