为了更好的阅读体检，可以查看我的算法学习网站
在线评测链接:P1189

题目内容

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

样例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$ 。

思路

二分答案

要求在保证客户端请求的数量不会超过核心购物系统的最大调用量的情况下，使得阈值 $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$的范围是相同的，所以时间复杂度可以简化为该结果)，这是该题能够接收的时间复杂度，因此二分答案的做法是可行的。

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

类似题目推荐

LeetCode

1.LeetCode 875. 爱吃香蕉的珂珂

2.LeetCode 2187. 完成旅途的最少时间

3.LeetCode 6325. 修车的最少时间

4.LeetCode 2226. 每个小孩最多能分到多少糖果

CodeFun2000

1. P1236 美团 2023.04.15-第二题-分糖果
2. P1106. 腾讯音乐 2023.3.23-第二题-划分字符串
3. P1006. 华为秋招 2022.9.21-数组取min
4. P1093. 米哈游 2023.03.19-第三题-塔子哥的无限字符串 - 难度较大

代码

CPP

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long longll a[100010],n;
ll th;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++;while(scanf("%lld",&a[n])!=EOF){++n;}n--;th=a[n];//最大调用量 n--;for(int i=1;i<=n;++i) sum+=a[i];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; else r=mid;}// check函数能够保证mid的值是合法的，因此最终l即为答案 printf("%lld",l);return 0;
}

python

a = [0] * 100010
n = 0
th = 0def check(value):# 验证答案正确性sum_val = 0for i in range(1, n + 1):if a[i] <= value:sum_val += a[i]else:sum_val += valuereturn sum_val <= thif __name__ == "__main__":sum_val = 0n += 1# 读取数据while True:try:a[n] = int(input())n += 1except EOFError:breakn -= 1th = a[n]n -= 1for i in range(1, n + 1):sum_val += a[i]if sum_val <= th:print("-1")exit(0)# 二分答案，采用开区间的二分方式 l = -1r = 100001while l + 1 < r:mid = (l + r) // 2if check(mid):l = midelse:r = mid# check函数能够保证mid的值是合法的，因此最终l即为答案print(l)

Java

import java.util.Scanner;public class Main {static long[] a;static int n;static long th;static boolean check(long value) {// 验证答案正确性long sum = 0;for (int i = 1; i <= n; ++i) {if (a[i] <= value)sum += a[i];elsesum += 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];if (sum <= th) {System.out.println("-1");return;}//二分答案，采用开区间的二分方式 int l = -1, r = 100001, mid;while (l + 1 < r) {mid = (l + r) >> 1;if (check(mid))l = mid;elser = mid;}// check函数能够保证mid的值是合法的，因此最终l即为答案 System.out.println(l);}
}

Go

package mainimport ("fmt"
)var a []int64
var n int
var th int64func 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 {break}a = append(a, num)}n = len(a) - 2th = a[n+1]sum := int64(0)for i := 1; i <= n; i++ {sum += a[i]}if sum <= th {fmt.Println("-1")return}//二分答案，采用开区间的二分方式 l, r := -1, 100001for l+1 < r {mid := (l + r) / 2if check(int64(mid)) {l = mid} else {r = mid}}// check函数能够保证mid的值是合法的，因此最终l即为答案 fmt.Println(l)
}

Js

const readline = require('readline');function check(value) {// 验证答案正确性let sum = 0;for (let i = 1; i <= n; i++) {if (a[i] <= value)sum += a[i];elsesum += 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];if (sum <= th) {console.log("-1");return;}//二分答案，采用开区间的二分方式 let l = -1, r = 100001, mid;while (l + 1 < r) {mid = Math.floor((l + r) / 2);if (check(mid))l = mid;elser = mid;}// check函数能够保证mid的值是合法的，因此最终l即为答案 console.log(l);});
}main();

题目内容均收集自互联网，如如若此项内容侵犯了原著者的合法权益，可联系我: (CSDN网站注册用户名: 塔子哥学算法) 进行删除。