华为秋招 2023.10.11 编程题目与题解

发表于 2023-10-13 更新于 2023-11-11 分类于笔试阅读次数：本文字数： 2.1k 阅读时长 ≈ 2 分钟

1、计算最少流控请求数

服务器性能有限，对于突发请求，有时需要通过流控保护系统不受冲击。假设某服务器的系统要求任意\(M\)分钟内只能处理\(N\)条请求，超出的请求必须流控掉。已知连续\(X\)分钟，每分钟的实际请求数，请给出至少流控掉多少请求，才能保证上述系统不受冲击。

输入

第一行：\(M\)和\(N\)，\(M\)范围\([1,10]\)；\(N\)的范围\([0,10000]\)

第二行：连续分钟数\(X\)，\(X\)范围为\([1,100000]\)

第三行：每分钟的请求数范围\([0,1000]\)

输出

最少可以流控的请求数。

样例

输入：
4 6
6
2 1 2 2 3 2


输出：
3

提示：
第一行系统要求：每4分钟只能接受6个请求。
第二行：连续6分钟。
第三行：每分钟的实际请求数。
至少流控3个请求(可以是： 第4分钟流控1个请求，第5分钟流控1个请求，第6分钟流控1个请求)，才可以满足系统4分钟内只能处理6条请求的要求。

输入：
2 10
6
1 9 1 9 8 2

输出：
7

提示：
第一行系统要求：每2分钟只能接受10个请求
第二行：连续6分钟。
第三行：每分钟的实际请求数。
至少流控7个请求(可以是第5分钟流控7个请求)，才可以满足系统2分钟内只能外理10条请求的要求。

解答

这题可以使用贪心轻易解决。从小到大枚举每个长度为\(m\)的区间，如果当前确实必须要流控一些请求，那么按照贪心的思想，应该优先流控掉这些请求，这确保了后面的请求能过尽量少流控一些。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],n;
int main(){
    int m,n,x;
    scanf("%d %d %d",&m,&n,&x);
    m=min(m,x);
    for(int i=1;i<=x;i++)
        scanf("%d",&a[i]);
    int sum=0;
    for(int i=1;i<=x;i++)
        sum+=a[i];
    int s=0;
    for(int i=1;i<m;i++)
        s+=a[i];
    for(int i=m;i<=x;i++){
        s+=a[i];
        for(int j=i;j>=i-m+1&&s>n;j--){
            int v=max(0,min(s-n,a[j]));
            a[j]-=v;s-=v;
        }
        s-=a[i-m+1];
    }
    int sum2=0;
    for(int i=1;i<=x;i++)sum2+=a[i];
    printf("%d\n",sum-sum2);
}

2、快乐时间

小明在工作之余喜欢在电子书城阅读不同的书籍并且获得最大的满足感，因此根据书城针对每本书籍的评分收集了\(n\)个书籍的打分清单books，例如第一本书的打分books[0]=5代表该书的满意程度为\(5\)，第二本书books[1]=-2代表该书的满意程度为\(-2\)。

阅读每本书花费的都是\(1\)单位时间，time定义为阅读本书及之前所有书的时间之和。因此第一本阅读的书籍time[0]=1，第二本阅读的书籍time[1]=2，第三本阅读的书籍time[2]=3并以此类推。

每本书籍的【快乐时间】系数为阅读该书籍和之前每本书籍所花费的时间乘以对这本书籍的满意程度，即time[i] * books[i]，其中\(i\)从\(0\)开始。

小明想了解自己如何安排阅读计划才能获得最大的快乐时间，请帮忙计算一下阅读给定书籍【快乐时间】总和最大的值是多少，可以按照任意顺序调整阅读书籍顺序（即每本书对应的time[i]是可以对调的），也可以放弃阅读某些书籍。

输入

输入为字符串，字符串内容为代表每本书籍的喜爱指数，例如books = [4,3,2]，其中\(1\le n\le -500\)，满意程度 \(-1000 \le \texttt{books[i]}\le -1000\)。

输出

输出为数字，代表最大的快乐时间，例如\(20\)，按照原来顺序相反的时间阅读书籍\((2\times 1 + 3\times2 + 4\times3 = 20)\)，评分越高的书籍越后面阅读可以获得最大的快乐时间。

样例

输入：
4,3,2

输出：
20

提示：
按照原来顺序相反的时间阅读书籍(2 * 1 + 3 * 2 + 4 * 3 = 20)，评分越高的书籍越后面阅读可以获得最大的快乐时间。

输入：
-1,-4,-5

输出：
0

提示：
大家对于这些书籍评分都很低，所以不阅读任何书籍可以获得最大的快乐时间。

输入：
-1,-8,0,5,-9

输出：
14

提示：
去掉第二个和最后一本书籍，最大的快乐时间系数和为(-1 * 1 + 0 * 2 + 5 * 3 = 14)。每本书籍都需要花费1单位时间来阅读。

解答

这题是一道经典的贪心题。由于快乐值前面的系数time[i]都是非负整数，因此如果需要不选择一些书，那么优先去掉满意度最小的那些书。那么问题转化为最大值\(s=\displaystyle{\sum_{i=1}^m i\cdot a_i}\)，其中\(a_i\)是被选定书籍的评分。可以发现，当我们\(a_i\)是不下降的时候，\(s\)值能过取得最大，因为如果存在一对\(a_j,a_i(j<i)\)使得\(a_j>a_i\)，交换它们会使得答案更优。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],n=0;
int main(){
    string s;
    cin>>s;
    for(char &ch:s){
        if(!isdigit(ch)&&ch!='-') ch=' ';
    }
    stringstream ss;
    ss<<s;
    while(ss>>s){
        a[++n]=atoi(s.c_str());
    }
    sort(a+1,a+n+1,greater<int>());
    int s1=0,s2=0,ans=0;
    for(int i=1;i<=n;i++){
        s1+=a[i];
        s2+=s1;
        ans=max(ans,s2);
    }
    printf("%d\n",ans);

}

3、稀疏存储

在虚拟化技术、芯片仿真器等领域，存在一种场景，即实际读写的数据量比较小，但要求可访问的地址空间却很大(要求4GB、甚至128GB地址空间)。

实现一个地址范围为32G的，可在该地址范围内任意位置读写数据的虚拟化内存机制(数据默认清零)。

对应功能：

读取任意地址数据；
往任意地址写入任意数据；
清空数据，并释放内存。

输入格式： Command Address Length Data

提示：

Command为Read、Write、Clear之一；
Address采用64位无符号十六进制数，全大写；
Length采用64位无符号十进制数，单位为“字节”；
Data采用字节流 (2个16进制数表示一个Byte)，全大写；
如果指定的Length大于实际给定的Data，需要程序自行未尾补0，小于则未尾截断。

输入

每条指令一行，一个用例输入可以是多条指令混合，只有Read指令有输出。

每个用例保证指令、参数格式正确，但不保证参数范围，需要程序按照题目规格要求自行校验，参数不合法，则对应的指令无效。

每个用例保证需要存储的总数据量最大不超过16MB。一个用例最多不超过\(500\)条指令。

例如（3表示有3条指令）

3
Write 0x100 7 001122AA
Read 0x100 4
Clear

输出

采用字节流 (2个16进制数表示一个Byte)，全大写。

例如

001122AA

每条Read指令对应一行输出数据，如果指令给的参数不合法，对应的输出为空（不换行）。

样例

输入：
1
Read 0x100 4

输出：
00000000

提示：
0x100地址空间未被写入数据，默认返回全0，一共4个字节。

输入：
3
Write 0x100 8 00001122AABBCCDD
Read 0x100 12
Clear

输出：
00001122AABBCCDD00000000

提示：
0x100地址，前8个字节被写入了有效数据00001122AABBCCDD，读取0x100地址12个字节数据，后4个字节补齐默认数据0，因此结果为00001122AABBCCDDO0000000。

解答

这题的地址值上限为32G，即地址范围是\(0\sim 2^{35}-1\)，令\(M=2^{35}\)。

为了方便操作，这里直接使用一个字典来存储对应位置的字节值（由于存储的数据量不超过16MB，因此字典最多只有\(2^{24}\)个项，在接受范围之内），每次进行Clear操作就清空字典，执行Write操作时，将每个字节对应的位置直接写入即可；在进行Read操作时，直接从字典中取值，如果取不到，那么用00字节替代。

以下是本代码校验时需要注意的地方：

Write操作时，需要注意给定字节串的长度是否为偶数。
Write操作和Read操作时，需要判断地址是否产生溢出，以及输入的长度Length是否是一个非负整数。
Read操作时，如果Length的值为\(0\)，那么不进行任何操作。

代码

n = int(input())
mp = dict()
MAX = 32 << 30
for _ in range(n):
    ls = input().split()
    if ls[0] == 'Clear':
        mp.clear()
    elif ls[0] == 'Write':
        add, sz, s = int(ls[1][2:], 16), int(ls[2]), ls[3]
        if sz < 0 or add + sz - 1 >= MAX or len(s) & 1:
            continue
        sz = min(sz, len(s) >> 1)
        s = s[:sz << 1]
        for i in range(sz):
            mp[add + i] = s[i << 1:i << 1 | 1]
    elif ls[0] == "Read":
        add, sz = int(ls[1][2:], 16), int(ls[2])
        if sz <= 0 or add + sz - 1 >= MAX:
            continue
        for i in range(sz):
            print(mp.get(add + i, "00"), end='')
        print()