本题为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$ 。

二分答案

1.化简题意

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

2.观察性质

1.条件一定能满足:设定 $v = 0$ , $sum(min(v,R_i))= 0$

2.$v$越大 , 条件越难满足: $v \rightarrow \infty$ , 那么就不会有$R_i$ 被取$min$ , 这个时候总和是最大的。

上述是考虑两个极端情况，也是最容易理解的情况。但是相信大家能够感受到单调性了： 随着 $v$ 的增大 , 总和就会增大，那么条件$T$ 就越难成立。

3.图形化显示

为了能够更直观的显示单调性，我们规定: 条件不满足时，$T = 0$ 。条件满足时$T = 1$ 。那么可以想象这个$T$应该随着$v$的增大，先$1$ 后 $0$ , 如图所示:

分析

题目要寻找的正是断崖下降的那个断崖点。 从另一个角度来说，我们的问题就变成了，<给你一个先1后0的数组，你需要找到最后一个$1$的位置>，这不正是二分搜索可以解决的问题么？只不过注意一点：这里的数组更加抽象，因为我们没办法直接$O(1)$获取这个数组里的每一个数，而是需要通过一定的计算来获取数组里每个元素的值。

至此，通过一步一步的分析，拨开云雾之后，大家可以明白 二分答案本质还是二分搜索。只不过我们二分的横坐标是答案。 而原先二分搜索的横坐标通常是数组下标。

4.解决思路

1.二分$v$ 来找数组里的最后一个1

2.获取“数组”里这个位置的值：对于每个确定的$v$ , 我们直接求解$\sum min(R_i,v) \leq cnt$ 这个逻辑表达式。成立返回1，不成立返回0

5.代码实现

# 读入
R = list(map(int,input().split()))
cnt = int(input())
# 查询数组里的第i位值
def check (i):
    su = 0
    for x in R:
        su += min(i , x)
    return su <= cnt
# 设定v的边界
l , r = 0 , 10**9
while l <= r:
    mid = l + r >> 1
    if check(mid):
        l = mid + 1
    else:
        r = mid - 1
# 这种情况即题目描述的第一种情况,等价于"数组"全1 , 那么右端点不会动
if r == 10**9:
    r = -1
print(r)

总结

1.二分答案，顾名思义，针对答案的二分。

2.它是一种更加抽象(广义)的二分搜索，所以学习它需要二分搜索作为前置知识。

3.解题关键:

• 1.化简题意，寻找答案 和 要满足的条件 $T$

• 2.判断条件$T$ 是否根据答案具有单调性(令成立为$1$ , 不成立 为 $0$)

• 3.转化成二分搜索(先1后0的数组找最后一个1 / 先0后1的数组找第一个1)