💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍊 01.LYA 的魔法宝石

问题描述

LYA 是一位热爱收藏魔法宝石的女孩。她希望收集 颗宝石，并且要求这些宝石的魔法值两两不相等。此外，所有宝石的魔法值的最大公约数必须为 。

为了尽可能节省购买成本，LYA 希望选择魔法值之和最小的宝石组合。请你帮助 LYA 计算并输出宝石魔法值之和的最小值。

输入格式

输入包含两个正整数 和 ，分别表示宝石的数量和魔法值的最大公约数。

输出格式

输出一个正整数，表示满足条件的宝石魔法值之和的最小值。

样例输入

3 2

样例输出

12

数据范围

题解

本题可以通过构造法来解决。为了让宝石的魔法值之和最小，我们可以将魔法值构造为 的倍数，并且按照从小到大的顺序选择。

具体步骤如下：

1. 初始化结果变量 为 ，表示宝石魔法值之和。
2. 从 到 遍历每个宝石：
   • 计算当前宝石的魔法值 。
   • 将 累加到结果变量 中。
3. 输出结果变量 的值。

时间复杂度：，其中 为宝石的数量。 空间复杂度：。

参考代码

• Python

n, k = map(int, input().split())
res = 0
for i in range(1, n + 1):
    temp = i * k
    res += temp
print(res)

• Java

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int k = in.nextInt();
        long res = 0;
        for (int i = 1; i <= n; i++) {
            long temp = i * k;
            res += temp;
        }
        System.out.println(res);
    }
}

• Cpp

#include <iostream>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    long long res = 0;
    for (int i = 1; i <= n; i++) {
        long long temp = i * k;
        res += temp;
    }
    cout << res << endl;
    return 0;
}

🌲 02.卢小姐的布料选购计划

问题描述

卢小姐是一位服装设计师,她计划从一家面料商那里购买一段布料用于设计新款连衣裙。商家提供了一卷总长为 米的布料,但其中只有某些区间的布料质地符合要求。

商家允许卢小姐从这卷布料中选择一段长度为 米的连续区间购买。卢小姐希望在选定的区间内,符合要求的布料段总长度尽可能长。请你帮助卢小姐计算,最优方案下可以购得多少米符合要求的布料。

输入格式

第一行输入三个正整数 ,分别代表布卷的总长度、布卷上符合要求的布料段数量以及卢小姐计划购买的布料长度。

接下来的 行,每行输入两个正整数 ,表示第 段符合要求的布料的起始位置和终止位置(单位:米)。

输出格式

输出一个整数,表示最优方案下可以购得的符合要求的布料总长度。

样例输入

10 3 6
1 3
4 5
7 9

样例输出

4

数据范围

• 
• 
• 
• 符合要求的布料段之间互不重叠。

题解

本题可以使用双指针滑动窗口的方法求解。我们可以枚举购买布料的左端点,并维护一个右端点,使得当前窗口内的布料长度不超过 。在枚举过程中,我们统计窗口内符合要求的布料段长度之和,并更新答案。

具体步骤如下:

1. 将所有符合要求的布料段按照起始位置从小到大排序。
2. 初始化左右指针 和 ,表示当前枚举的区间范围。
3. 遍历布料段,将右指针 不断右移,直到当前区间长度超过 或遍历完所有布料段。
4. 统计当前区间内符合要求的布料段长度之和 ,更新答案。
5. 如果右指针 已经到达最后一个布料段,直接更新答案;否则,计算当前区间右端点与下一个布料段左端点之间的空白部分长度 ,更新答案为 。
6. 将左指针 右移一个布料段,同时将 减去对应的布料段长度,继续枚举下一个区间。

时间复杂度为 ,其中排序的时间复杂度为 ,双指针遍历的时间复杂度为 。空间复杂度为 。

参考代码

• Python

class Solution:
    def maxCoverLength(self, n: int, m: int, k: int, segments: List[List[int]]) -> int:
        segments.sort()
        ans = cover = 0
        left = right = 0
        
        while right < m:
            while right < m and segments[right][1] - segments[left][0] <= k:
                cover += segments[right][1] - segments[right][0]
                right += 1
            
            if right == m:
                ans = max(ans, cover)
            else:
                remain = max(0, segments[left][0] + k - segments[right][0])
                ans = max(ans, cover + remain)
            
            cover -= segments[left][1] - segments[left][0]
            left += 1
        
        return ans

• Java

class Solution {
    public int maxCoverLength(int n, int m, int k, int[][] segments) {
        Arrays.sort(segments, (a, b) -> a[0] - b[0]);
        int ans = 0, cover = 0;
        int left = 0, right =