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

发表于 2023-09-28 分类于笔试阅读次数：本文字数： 1.9k 阅读时长 ≈ 2 分钟

1、价格优惠

某商城进行“双十一”促销活动，活动采用等价格减免的方式，某位客人一次购买了\(N\)件商品，需要帮忙计算本次购买能获得的总优惠。给定商品价格数组\(p\)，其中\(p[i]\)表示第i件商品的价格，第\(i\)件商品能获得的优惠为第\(i\)件商品之前的第\(j\)件商品的价格，其中\(p[j]\le p[i]\)，并目\(j\le i\)，且\(p[j]\)是离\(p[i]\)最近的一个小于等于\(p[i]\)的商品。求本次购买能获得的总优惠。

例如：给定价格数组\(p=[9,4,3,5],p[3]=5\)能获得的优惠为\(p[2]=3,p[2]\)是满足条件离\(p[3]\)最近的一个商品，其中\(p[1]=4\)也小于\(p[3]\)，但不是离\(p[3]\)最近的商品。

输入

第一行是商品的个数\(N,1\le N\le 100000\)。

第二行是用空格分隔的\(N\)个整数，数组元素的值表示商品的价格\(0< p[i]\le 100000\)。

例如：

1 2	5 9 4 5 2 4

输出

输出为一个整数，表示本次购买获得的总优惠。

例如：

样例

输入：
5
9 4 5 2 4

输出：
6

提示：
商品0的价格为p[0]=9，第一件商品之前无其他商品，该商品获得的优惠为0。
商品1的价格为p[1]=4，p[1]之前不存在满足条件的商品，该商品获得的优惠为0。
商品2的价格为p[2]=5，p[2]之前满足条件的最近的一个商品为p[1]=4，该商品获得的优惠为4。
商品3的价格为p[3]=2，p[3]之前没有满足条件的商品，该商品获得的优惠为0。
商品4的价格为p[4]=4。p[4]之前满足条件的最近的一个商品为p[3]=2，该商品获得的优惠为2。
由此可以计算出本次购买可以获得的总优惠为： 4+2=6。

输入：
4
1 2 3 5

输出：
6

提示：
商品0的价格为p[0]=1，第一件商品之前无其他商品，该商品获得的优惠为0。
商品1的价格为p[1]=2，p[1]之前满足条件的最近的一个商品为p[0]=1，该商品获得的优惠为1。
商品2的价格为p[2]=3，p[2]之前满足条件的最近的一个商品为p[1]=2，该商品获得的优惠为2。
商品3的价格为p[3]=5，p[3]之前满足条件的最近的一个商品为p[2]=3，该商品获得的优惠为3。
由此可以计算出本次购买可以获得的总优惠为：1+2+3=6。


输入：
4
4 3 2 1

输出：
0

提示：
商品0的价格为p[0]=9，第一件商品之前无其他商品，该商品获得的优惠为0。
商品1的价格为p[1]=4，p[1]之前不存在满足条件的商品，该商品获得的优惠为0。
商品2的价格为p[2]=5，p[2]之前满足条件的最近的一个商品为p[1]=4，该商品获得的优惠为4。
商品3的价格为p[3]=2，p[3]之前没有满足条件的商品，该商品获得的优惠为0。
商品4的价格为p[4]=4。p[4]之前满足条件的最近的一个商品为p[3]=2，该商品获得的优惠为2。
本次购买每件商品都没有满足条件的优惠，本次购买可获得的优惠为0。

解答

本题是Leetcode 496的变种。相当于是为每一个数\(p[i]\)找到左边第一个不超过它的数，并加上它。

因此，使用单调栈可以完美解决这个问题，我们通过维护一个非单调递减的栈来记录元素的值，当把栈中所有比当前元素大的元素弹出后，栈顶即为我们所需要求的值，再把当前的数推进栈中。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
int p[N],n;
int main(){
    stack<int>st;
    ll ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&p[i]);
    for(int i=1;i<=n;i++){
        while(!st.empty()&&p[i]<st.top()) st.pop();
        if(!st.empty())
            ans+=st.top();
        st.push(p[i]);
    }
    printf("%lld\n",ans);
}

2、多项式计算

给定两个一元多项式以及多项式运算符，计算输出两个多项式运算的结果，计算规则见样例。

输入

分三行输入，第一行输入多项式\(A\)的系数数组（按照阶数高到低顺序），第二行输入多项式\(B\)的系数数组，第三行输入多项式运算符。运算符包括加(+)减(-)乘(*)三种，系数数组大小小于\(128\)，系数取值范围\([-512,512]\)。

输出

输出多项式运算结果的系数数组，如果计算后多项式为\(0\)，则输出0。从第\(1\)个非零的系数开始输出。

样例

输入：
[1 2 3 4 5 6]
[2 3 -4]
+

输出：
[1 2 3 6 8 2]

提示：
多项式系数数组[1 2 3 4 5 6]表示多项式A(x)=x^5 + 2x^4+ 3x^3 + 4x^2 + 5x + 6
多项式系数数组[2 3 -4]表示多项式B(x)=2x^2 + 3x - 4
A(x) + B(x) = x^5 + 2x^4 + 3x^3 + 6x^2 + 8x + 2，对应的多项式系数数组为[1 2 3 6 8 2]。

输入：
[1 2 3]
[1 2 1]
-

输出：
[2]

提示：
(x^2 + 2x + 3) - (x^2 + 2x + 1) = 2
高阶的0系数不输出。

输入：
[1 1]
[1 1]
*

输出：
[1 2 1]

提示：
(x + 1) * (x + 1) = x^2 + 2x + 1

解答

本题是一道输入输出处理题和模拟题。建议使用python结合eval函数来完成。接下来为了方便处理按照多项式的形式进行处理，需要将输入的数组\(A,B\)进行逆序。

逆序完成后，我们可以将下标作为指数，按照多项式的定义进行计算。

需要注意的是，计算完多项式的结果后，按照题目要求需要注意如下事项：

去掉高次中的\(0\)系数项。
如果多项式的结果为\(0\)，那么还需要避免输出的多项式为空，需要往对应数组添加回一个\(0\)。
对输出的多项式进行逆序。

代码

A = list(reversed(eval(input().replace(' ', ','))))
B = list(reversed(eval(input().replace(' ', ','))))
op = input()
n = max(len(A), len(B))
A += [0] * (n - len(A))
B += [0] * (n - len(B))
if op == '+':
    C = [A[i] + B[i] for i in range(n)]
elif op == '-':
    C = [A[i] - B[i] for i in range(n)]
else:
    C = [0 for i in range(n + n)]
    for i in range(n):
        for j in range(n):
            C[i + j] += A[i] * A[j]
while len(C) > 0 and C[-1] == 0:
    C.pop()
if len(C) == 0:
    C = [0]
C.reverse()
print(str(C).replace(', ', ' '))

3、货物运输

有\(m\)件货物和\(n\)辆卡车，每辆卡车只能运送一件货物，卡车的载重量需要大于等于货物重量才能运输；

另有\(x\)个载重为\(y\)的拖斗，每辆卡车最多可以拖挂一个拖斗以提升载重量，共同运输一件更重的货物；

请你返回最多可以运输多少件货物。

输入

三行数据：

1
2
3

m n x y
weight0 weight1 weight2...
load0 load1 load2...

第\(1\)行包含四个数字，分别为：

\(m\)：货物数量
\(n\)：卡车数量
\(x\)：拖斗数量
\(y\)：拖斗载重

第\(2\)行为货物的重量列表，以空格分隔；

第\(3\)行为卡车的载重列表，以空格分隔；

范围：

\(1\le\) 货物/卡车\(\le 50000\)
\(0\le\) 拖斗数量\(\le 50000\)
\(0\le\) 货物重量/卡车载重量/拖斗载重量\(\le 1000000000\)

输出

一个整数，最多可以运输货物的数量。

样例

输入：
5 5 1 5
5 5 8 9 9
1 2 4 6 6

输出：
3

提示：
2号卡车运输1号货物，6>=5
4号卡车运输5号货物，6>=5
5号卡车挂拖斗，运输3号货物，4+5>=8

输入：
4 4 2 3
9 6 7 8
5 2 3 4

输出：
2

提示：
1号卡车挂拖斗，运输4号货物，5+3>=8
4号卡车挂拖斗，运输3号货物，4+3>=7

解答

这道题是Leetcode 2071的原题。按照贪心的思想，如果我们可以完成\(k\)个货物的运输，那么用载重最重的\(k\)辆卡车运送\(k\)个最轻的货物必定是一个解（包括使用拖斗），并且这个解是最极端的情况。

如果能够运送\(k\)件货物，那么就存在一个运送\(k-1\)个货物的方案，因此这道题我们可以使用二分进行求解。

现在需要判断\(k\)件货物是否能够被运送。我们将使用载重最大的\(k\)辆卡车运送最轻的\(k\)个货物。我们从小到大遍历每个货物，每个货物用一个载重比它大，且最载重最小的卡车运行，这才符合我们贪心地思想。如果当前卡车并不能运送当前货物，那么在此之后它也不能够运送其它货物，他这时需要一个拖斗才能够运送，我们需要为这辆卡车添加一个拖斗，并且延后它的使用时期。如果这辆卡车装了拖斗依旧不能运送这个货物，那么说明这个\(k\)不可行。最终，我们只需要判断拖斗的使用数量是否不超过\(x\)即可。

此外还需要注意的是，如果一个卡车已经装载了拖斗后，和另一个没装拖斗的卡车载重相等，那么优先使用前一个卡车，因为后一个仍然有提升载重的潜力。

代码

# include <bits/stdc++.h>
# define pi pair<int,int>
using namespace std;
typedef long long ll;

const int N=100004;

int w[N],l[N],n,m,x,y;
bool ok(int k){
    int cnt=0;
    priority_queue<pi,vector<pi>,greater<pi>>q;
    for(int i=1;i<=k;i++)
        q.push(pi(l[n-k+i],1));
    for(int i=1;i<=k;){
        auto [ld,tp]=q.top();q.pop();
        if(ld>=w[i]){
            i++;
        }
        else if(tp==0) return 0;
        else{
            ++cnt;
            q.push(pi(ld+y,0));
        }
    }
    return cnt<=x;
}
int main(){
    scanf("%d %d %d %d",&m,&n,&x,&y);
    for(int i=1;i<=m;i++)
        scanf("%d",&w[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&l[i]);
    sort(w+1,w+m+1);
    sort(l+1,l+n+1);
    ok(3);
    int l=0,r=min(m,n);
    while(l<r){
        int mid=(l+r+1)>>1;
        if(ok(mid)) l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
}