塔子哥学算法

B站视频精讲:P1189 (opens new window) 在线评测链接:P1189 (opens new window)

# 题目内容

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

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

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

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

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

# 输入描述

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

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

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

# 输出描述

调用量的阈值 valuevalue

# 样例

输入

1 4 2 5 5 1 6 
13

输出

2

样例解释

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

# 样例2

输入

1 7 8 8 1 0 2 4 9
7

输出

0

样例解释

因为即使 valuevalue 设置为 11 , 1+1+1+1+1+1+1+1=8>71+1+1+1+1+1+1+1=8>7 也不满足，所以 valuevalue 只能为 00 。

split

# 思路

# 二分答案

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

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

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

# 单调性

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

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

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

# 答案验证

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

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

# 类似题目推荐

# LeetCode

1.LeetCode 875. 爱吃香蕉的珂珂 (opens new window)

2.LeetCode 2187. 完成旅途的最少时间 (opens new window)

3.LeetCode 6325. 修车的最少时间 (opens new window)

4.LeetCode 2226. 每个小孩最多能分到多少糖果 (opens new window)

# CodeFun2000

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

# 代码

# CPP

#include <iostream>
#include <cstdio>
using namespace std;
#define ll long long

ll 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 = 0

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
    # 读取数据
    while True:
        try:
            a[n] = int(input())
            n += 1
        except EOFError:
            break
    n -= 1
    th = a[n]
    n -= 1
    for i in range(1, n + 1):
        sum_val += a[i]
    if sum_val <= th:
        print("-1")
        exit(0)
    # 二分答案，采用开区间的二分方式 
    l = -1
    r = 100001
    while l + 1 < r:
        mid = (l + r) // 2
        if check(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;

    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];
        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;
            else
                r = mid;
        }
        // check函数能够保证mid的值是合法的，因此最终l即为答案 
        System.out.println(l);
    }
}

# Go

package main

import (
	"fmt"
)

var a []int64
var n int
var th int64

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 {
			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]
	}
	if sum <= th {
		fmt.Println("-1")
		return
	}
    //二分答案，采用开区间的二分方式 
	l, r := -1, 100001
	for l+1 < r {
		mid := (l + r) / 2
		if 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];
        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];
        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;
            else
                r = mid;
        }
        // check函数能够保证mid的值是合法的，因此最终l即为答案 
        console.log(l);
    });
}

main();

← 第2题-获取最多食物 →