华为暑期实习 2023.05.31 机试题目与题解

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

1、获取网络忙时数据

工程师小王想要从海量的网络数据中，筛选出忙时数据。由于是海量数据，小王没办法对海量数据进行排序，再取topN的忙时数据(将数据从大到小排序，取前N个)。聪明的小王想到了使用固定大小的优先级队列来进行数据筛选。为了场简化，我们用正整数集来表示海量的网络数据，同时只取N个忙时数据，也即只取\(N\)个最大的正整数。针对每一批数据输入，单独输出一行结果，直接将\(N\)个正整数拼接完完整的一行字符串输出即可。

输入

第一行是正整数\(N\)和\(M\)，\(N\)为忙时个数，取值范围\([1,24]\)，\(M\)为输入的数据行数，范围\([1,1000]\)；

接下来\(M\)行，每行两个正整数\(A,B\)，以空格分隔，表示有\(A\)个重复的正整数\(B\)，\(A\)、\(B\)的取值范围\([1,2147483647]\)。

输出

输出每增加一批数据对应的队列结果，直接将队列里的所有数据集从大到小拼接成字符串输出。 ## 样例

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

输出：
5
533
533
544
654

提示：
第一次输入1个5，则队列输出为5
第二次输入6个3，则队列输出为533
第三次输入2个2，则队列输出为533
第四次输入5个4，则队列输出为544
第五次输入1个6，则队列输出为654

解答

本题采用了一种比较朴素的做法。首先将\(\min(n,a)\)个数\(b\)拼接到原数组\(A\)中，进行排序，取前\(n\)个最大并输出即可，其余数将会被抛弃，因为它们在以后肯定不会再被输出。

代码

A = []
n, m = map(int, input().split())
for _ in range(m):
    a, b = map(int, input().split())
    A = list(reversed(sorted(A + [b] * min(n, a))))[:n]
    print("".join(str(x) for x in A))

2、园区规划

公司购买一块\(m\times n\)大小的地皮，用于建设新园区。现要将这块地皮规划为多个正方形区域。出于成本考虑。规划的正方形区域的个数越少越好。即所有区域应纳入规划。请你帮助计算一下，最少能规划多少区域？

输入

第一行，仅包含一个整数，代表\(m\)。

第二行，仅包含一个整数，代表\(n\)。

其中\(1\le n\le 13,1\le m\le 13\)

输出

一行，仅包含一个整数，表示最少能规划块区域的数量。

样例

输入：
3 2

输出：
3

输入：
13 11

输出：
6

解答

看到数据范围\(n,m\)不超过\(13\)，我们可以想到使用搜索算法来做，只需要写两个函数用来判断正方形是否有格子被填充和填充整个正方形即可。这里的搜索使用了如下技巧：

为了使结果快速收敛，每次尝试填入最大的正方形，依次将长度递减。
为了防止重复枚举，所有正方形的左上角坐标必须是按某一个顺序进行遍历的。这里的顺序是以行下标为第一关键字，列下标为第二关键字。

代码

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

const int N=174;
int x[N],y[N],n,m;
int vis[15][15];
int ans=1e9;
bool check(int x,int y,int k){
    for(int i=x;i<x+k;i++)
        for(int j=y;j<y+k;j++)
            if(vis[i][j]) return 0;
    return 1;
}
void draw(int x,int y,int k,int c){
    for(int i=x;i<x+k;i++)
        for(int j=y;j<y+k;j++)
            vis[i][j]=c;
}
void dfs(int f,int pos){
    if(f>=ans) return;
    if(pos==n*m+1){
        ans=f;return;
    }
    int l=min(n-x[pos]+1,m-y[pos]+1);
    int k;
    for(k=l;k>0&&!check(x[pos],y[pos],k);k--);
    for(;k>0;k--){
        draw(x[pos],y[pos],k,1);
        int q=pos;
        for(;q<=n*m&&vis[x[q]][y[q]];q++);
        dfs(f+1,q);
        draw(x[pos],y[pos],k,0);
    }
}
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1,p=0;i<=n;i++)
    for(int j=1;j<=m;j++){
        x[++p]=i;y[p]=j;
    }
    dfs(0,1);
    printf("%d\n",ans);
}

3、太阳能发电站利润评估

某公司计划在A地区选择一片区域投资建设大阳能发电站。由于太阳能发电与地形、光照等自然条件强相关，因此在建设前，需要先进行建站选址、确定安装大阳能板的数量，让发电利润最大。

发电站每年的利润可以用以下公式计算： \(\displaystyle{\sum_{i=1}^N K_i-N\times C}\) 其中: \(K_i\)：表示第\(i\)个太阳能板的年发电收入。与太阳能板安装位置的自然条件（光照等）有关。 \(N\)：表示太阳能板总数量。 \(C\)：表示平均每个太阳能板每年的支出费用 (老化损耗、维修等) ，取固定值：5。

整个A地区是一个矩形区域。前期技术人员，按照一块太阳能板覆盖的面积，将A地区内部划分为\(m\times n\)个地块提前勘测并计算出每一个地块的年发电收入，使用\(m\times n\)的发电收入矩阵表示。为了减少管理成本，充分利用土地，必须选择一个矩形区域进行排列安装。请实现功能，求出发电站应安装多少块太阳能板，年利润最大，最大为多少。

输入

第一行包含两个正整数：m、n，空格分隔。表示A地区分成的\(m\times n\)个地块；0 < m、n < 1024。后续n行，每行m个正整数，空格分隔。表示每个小块区域的太阳能板年发点收入。0 <= 收入 < 100。

输出

两个整数值，空格分隔。第一个值表示安装得太阳能板总量，第二个值表示最大利润。注意：

如果存在最大利润都相同的情况，则输出太阳能板总量较小的结果。
如果所有地块利润都是负数，则需选择损失最少的那个地块，安装一块太阳能板。

样例

输入：
3 2
4 10 7
3 2 9

输出：
4 8

提示：
4 [10] [7]
3 [2] [9]

选择的是：10、7、2、9这一正方形区域的4个地块。利润是(10 + 7 + 2 + 9) - (4 * 5) = 8。

输入：
2 2
1 2
3 4

输出：
1 -1

提示：
1 2
3 [4]

解答

可以将原来的式子写成\(\displaystyle{\sum_{i=1}^N(K_i-C)}\)。令\(K_i'=K_i-C\)，整道题相当于就是求最大子矩阵。

这里给出的算法是时间复杂度为\(O(nm\min(n,m))\)的算法（为了保证运行时间足够低，如果\(n>m\)，那么将整个矩阵进行转置）。

令\(\displaystyle{S[i,j]=\sum_{k=1}^n A[k,j]}\)，那么考虑每一对上下边界\(0\le u<d\le n\)，令\(B[j]=S[d,j]-S[u,j]\)。问题转化为对数组\(B\)求解最大子数组和，可以以线性的时间完成，并且在这一过程中，需要注意求解最少元素个数时，如果遇到一对不相等的\(p,p',p<p'\)，使得\(B\)的前\(p\)项和与\(B\)的前\(p'\)项和相等，那么左边界选择\(p'\)，因为它要求元素个数最少。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1030;
int s[N][N], n, m;
int main(){
    scanf("%d %d", &m, &n);
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            scanf("%d", &s[i][j]);
            s[i][j] = s[i][j] - 5;
        }
    }
    if (n > m){
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++)
                if (i < j)
                    swap(s[i][j], s[j][i]);
        swap(n, m);
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            s[i][j] = s[i - 1][j] + s[i][j];
    int ans = -2e9, cnt = 0;
    for (int d = 1; d <= n; d++){
        for (int u = 0; u < d; u++){
            int p = 0, mn = 0, sum = 0;
            for (int j = 1; j <= m; j++){
                int x = s[d][j] - s[u][j];
                sum += x;
                int y = (j - p) * (d - u);
                if (sum - mn > ans || sum - mn == ans && y < cnt){
                    ans = sum - mn;
                    cnt = y;
                }
                if (sum <= mn){
                    mn = sum;
                    p = j;
                }
            }
        }
    }
    printf("%d %d\n", cnt, ans);
}