【小米笔试题汇总】2024-03-23-小米春招笔试题

admin管理员组

文章数量:1540560

🍭 大家好这里是KK爱Coding ，一枚热爱算法的程序员

✨ 本系列打算持续跟新小米近期的春秋招笔试题汇总～

💻 ACM银牌🥈| 多次AK大厂笔试 ｜ 编程一对一辅导

👏 感谢大家的订阅➕ 和 喜欢💗

文章目录

• • 01.K 小姐的宴会安排
  • • • 问题描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 数据范围
      • 题解
      • 参考代码
  • 02.LYA 公主的庄园美化
  • • • 问题描述
      • 输入格式
      • 输出格式
      • 样例输入
      • 样例输出
      • 数据范围
      • 题解
      • 参考代码

01.K 小姐的宴会安排

问题描述

K 小姐是一位著名的社交名媛,她经常在家中举办各种宴会活动。这次,她将邀请 n n n 位好友出席宴会。每位好友都有一个 A A A 值和 B B B 值,分别代表这个人的魅力程度和社交能力。

K 小姐打算将所有来宾按照一定顺序安排入座。她希望能够安排一段连续的 k k k 位来宾,使得这 k k k 位来宾的魅力值都不小于 x x x,社交能力也都不小于 y y y。这样一来,在宴会过程中,这一小段来宾就能较好地互相交流,增进感情。

现在给定所有来宾的 A A A 值和 B B B 值,请你帮助 K 小姐计算一共有多少种不同的安排方案满足她的要求。

输入格式

第一行包含五个正整数 n , k , x , y , z n, k, x, y, z n,k,x,y,z,分别表示来宾总人数、连续来宾人数要求、魅力值下限要求、社交能力下限要求和一个额外的参数。

第二行共 n n n 个空格分开的正整数 A 1 , A 2 , . . . , A n A_1, A_2, ..., A_n A1​,A2​,...,An​,表示每个来宾的魅力值。

第三行共 m m m 个空格分开的正整数 B 1 , B 2 , . . . , B n B_1, B_2, ..., B_n B1​,B2​,...,Bn​,表示每个来宾的社交能力值。

输出格式

输出一个整数,表示满足 K 小姐要求的不同安排方案数。

样例输入

10 2 2 4 0
2 2 9 1 8 1 6 1 7 7  
4 8 5 1 9 4 1 3 9 4

样例输出

3

数据范围

• 1 ≤ n ≤ 80000 , 1 ≤ k ≤ n , 1 ≤ x , y ≤ 100000 , 0 ≤ z ≤ 1 1 \le n \le 80000, 1 \le k \le n, 1 \le x, y \le 100000, 0 \le z \le 1 1≤n≤80000,1≤k≤n,1≤x,y≤100000,0≤z≤1。

题解

这是一个滑动窗口的经典应用题目。我们需要维护两个单调队列,分别记录当前滑动窗口内最小的魅力值和最小的社交能力值。

具体做法是,我们从左往右遍历所有来宾,对于当前来宾 i i i,我们首先需要从两个单调队列中移除所有已经滑出窗口的元素。然后我们再分别从两个单调队列的末尾移除所有魅力值和社交能力值都大于等于当前来宾的元素。这样可以保证单调队列的首元素就是当前窗口内的最小值。

最后,如果当前滑动窗口的长度已经满足要求 k k k,那么我们就检查单调队列首元素对应的魅力值和社交能力值是否都满足下限要求。如果满足,就将方案数加一。

时间复杂度为 O ( n ) O(n) O(n),空间复杂度为 O ( n ) O(n) O(n)。

参考代码

• Cpp

#include <iostream>
#include <deque>
using namespace std;

int main() {
    int n, k, x, y, z;
    cin >> n >> k >> x >> y >> z;
    
    deque<int> a_deq, b_deq;
    int *a = new int[n], *b = new int[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        // Remove out-of-window elements
        if (!a_deq.empty() && i - k >= a_deq.front()) a_deq.pop_front();
        if (!b_deq.empty() && i - k >= b_deq.front()) b_deq.pop_front();
        
        // Remove greater or equal elements from back
        while (!a_deq.empty() && a[a_deq.back()] >= a[i]) a_deq.pop_back();
        while (!b_deq.empty() && b[b_deq.back()] >= b[i]) b_deq.pop_back();
        
        // Push current index to deques
        a_deq.push_back(i);
        b_deq.push_back(i);
        
        // Check if window size is k and values satisfy conditions
        if (i - k + 1 >= 0 && a[a_deq.front()] >= x && b[b_deq.front()] >= y) ans++;
    }
    
    cout << ans << endl;
    delete[] a;
    delete[] b;
    return 0;
}

02.LYA 公主的庄园美化

问题描述

在 LYA 公主的领地上,有一处风景秀丽的庄园。为了进一步美化这处庄园,公主决定对庄园内的一些山峰进行修整。公主拥有一种神奇的魔法,可以指定一段连续的山峰区域,将它们的高度统一降低到一个新的水平。

庄园内总共有 n n n 座山峰,公主最多可以施展魔法 m m m 次。每次施法时,她会指定一段连续的山峰区间 [ L , R ] [L, R] [L,R],以及要降低的高度 h h h。那么,第 L L L 座到第 R R R 座山峰的高度都会减少 h h h 米。

公主希望通过有限次的施法,至少能使一座山峰的高度降至海平面以下(高度小于等于 0)。她想知道,最少需要施法多少次才能实现这个目标。

输入格式

第一行包含两个正整数 n n n 和 m m m,分别表示山峰的数量和公主能够施法的最大次数。

第二行包含 n n n 个正整数 H 1 , H 2 , . . . , H n H_1, H_2, ..., H_n H1​,H2​,...,Hn​,表示每座山峰的初始高度。

接下来的 m m m 行,每行包含三个正整数 L , R , h L, R, h L,R,h,表示每次施法作用的山峰区间 [ L , R ] [L, R] [L,R] 以及降低的高度 h h h。

输出格式

输出一个整数,表示最少需要施法多少次,就能使至少一座山峰的高度降至海平面以下。

样例输入

5 4
6 5 3 4 6
1 3 2
4 4 2 
3 5 1
1 5 6

样例输出

3

数据范围

• 对于 1 ≤ n , m ≤ 1 0 5 1 \le n, m \le 10^5 1≤n,m≤105, 1 ≤ h , H i ≤ 1 0 9 1 \le h, H_i \le 10^9 1≤h,Hi​≤109, 1 ≤ L ≤ R ≤ n 1 \le L \le R \le n 1≤L≤R≤n 的输入数据,保证有解。

题解

我们可以使用二分查找的方法来解决这个问题。具体地,我们需要找到最小的 k k k 值,使得在施展 k k k 次魔法之后,至少有一座山峰的高度降至海平面以下。

我们可以定义一个检查函数 c h e c k ( k ) check(k) check(k),它模拟施展前 k k k 次魔法的过程,并判断是否至少有一座山峰的高度降至海平面以下。检查函数的实现方式是使用差分数组来更新山峰高度。

在二分查找的过程中,我们将查找范围 [ 1 , m ] [1, m] [1,m] 一分为二,对于中间值 m i d mid mid,我们调用 c h e c k ( m i d ) check(mid) check(mid) 函数判断是否满足条件。如果满足,那么我们将右边界移动到 m i d mid mid,否则将左边界移动到 m i d + 1 mid + 1 mid+1。最终得到的左边界值就是答案。

该算法的时间复杂度为 O ( m log ⁡ m ) O(m \log m) O(mlogm),空间复杂度为 O ( n ) O(n) O(n)。

参考代码

• Python

from collections import deque

def check(k, n, heights, operations):
    diffs = [0] * (n + 2)
    for i in range(k):
        l, r, h = operations[i]
        diffs[l] -= h
        diffs[r + 1] += h
    
    for i in range(1, n + 1):
        diffs[i] += diffs[i - 1]
    
    for i in range(n):
        if heights[i] + diffs[i + 1] <= 0:
            return True
    
    return False

n, m = map(int, input().split())
heights = list(map(int, input().split()))
operations = []
for _ in range(m):
    l, r, h = map(int, input().split())
    operations.append((l - 1, r - 1, h))

left, right = 1, m
while left < right:
    mid = (left + right) // 2
    if check(mid, n, heights, operations):
        right = mid
    else:
        left = mid + 1

print(left)

本文标签： 小米笔试