笔试时间：2024年09月28日 秋招

历史笔试传送门：2023秋招笔试合集

第一题

题目

小R过年收到了很多压岁钱，所以他想拿去买玩具。小R总共收到了 m 元压岁钱。商店里有10^9种玩具，种类编号为1~10^9，第i种玩具的价格为i元。但是小R已经有了其中n种玩具了，他不喜欢重复，所以每种玩具他最多只想拥有一个，已经有的就不会再买了，没有的也只会买最多一个。现在小R想知道他最多能再买多少种玩具。

输入描述

第一行两个整数 n,m，表示已有玩具的种类数和压岁钱数量。

接下来一行n个整数a1,a2,…an，表示小R拥有的所有玩具的编号。

对于 100% 的数据，2<=n<=100000,1<=ai,m<=10^9，保证ai,互不相同。

输出描述

输出一个整数表示小R最多能再买多少种玩具。

样例输入

5 16

2 5 9 10 100

样例输出

4

参考题解

贪心的选择，遇到已经存在的就跳过，直接遍历即可。

C++：[此代码未进行大量数据的测试，仅供参考]

#include<bits/stdc++.h>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    unordered_set<int> st;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        st.insert(x);
    }
    
    int cur = 1;
    int ans = 0;
    while (m >= cur) {
        if (st.count(cur)) {
            cur++;
            continue;
        }
        ans++;
        m -= cur;
        cur++;
    }
    
    cout << ans << "\n";
}

Java：[此代码未进行大量数据的测试，仅供参考]

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        
        Set<Integer> st = new HashSet<>();
        for (int i = 0; i < n; i++) {
            int x = sc.nextInt();
            st.add(x);
        }
        
        int cur = 1;
        int ans = 0;
        while (m >= cur) {
            if (st.contains(cur)) {
                cur++;