2023.04.12-暑期实习-第一题-购物系统的降级策略

TaZi SU @ 9 months ago

题目大意

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

思路

二分答案

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

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

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

单调性

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

当阈值 $value$ 变小时，更多的客户端发起的请求量会被限制，因此总的请求量就会减小
当阈值 $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(); // 调用主程序

ID

Time

1000ms

Memory

256MiB

Difficulty

Tags

二分

# Submissions

240

Accepted

Uploaded By

TaZi

1 solutions

题目大意

思路

二分答案

单调性

答案验证

代码说明

代码

CPP

python

Java

Go

Js

Information

Status

Development

Support