灵犀互娱笔试 灵犀互娱笔试题 0816
笔试时间：2025年8月16日
往年笔试合集：
第一题：矿工宝石采集
在一款名为"地下城探险"的挖矿游戏中，有n位矿工准备进入矿洞采集宝石。每位矿工都有一个挖掘能力值，代表他们能够挖掘的宝石硬度上限。
矿洞中有m颗宝石，每颗宝石都有一个硬度值。
每位矿工只能采集一颗宝石，且只能采集硬度不超过自己挖掘能力的宝石。为了最大化收益，矿主希望尽可能多地让矿工采集到宝石。
请你计算最多有多少位矿工可以成功采集到宝石。
输入描述
第一行输入两个整数 n 和 m，分别代表矿工的数量和宝石的数量。
第二行输入 n 个整数，表示每位矿工的挖掘能力值。
第三行输入 m 个整数，表示每颗宝石的硬度值。
输出描述
输出一个整数，表示最多有多少位矿工可以成功采集到宝石。
补充说明：0 ≤ n, m ≤ 1000 矿工能力值和宝石硬度值均为正整数，范围在[1, 1000]之间
样例输入
3 5
7 2 9
1 5 10 3 8
样例输出
3
参考题解
这是一个典型的贪心算法问题。为了让尽可能多的矿工采到宝石，我们应该优先满足能力较弱的矿工，让他们去采集硬度较低的宝石。因为能力强的矿工可以采集硬度高和硬度低的宝石，而能力弱的矿工选择范围很小。具体步骤如下：将矿工的挖掘能力值和宝石的硬度值分别从小到大进行排序。使用两个指针，一个指向能力最弱的矿工，另一个指向硬度最低的宝石。遍历所有矿工，对于当前矿工，我们尝试为他寻找硬度最低且他能开采的宝石。如果当前矿工的能力值大于或等于当前宝石的硬度值，则表示可以成功匹配。我们将成功匹配的矿工数加一，然后同时考虑下一位矿工和下一颗宝石。如果当前矿工的能力值小于当前宝石的硬度值，说明这位矿工无法开采这颗宝石（也无法开采后面更硬的宝石），所以我们只能寄希望于下一位能力更强的矿工来开采这颗宝石。因此，我们只移动矿工指针，宝石指针保持不变。当任何一个指针超出列表范围时，循环结束。
C++：
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
if (!(cin >> n >> m)) return 0;
vector<int> miners(n), gems(m);
for (int i = 0; i < n; ++i) cin >> miners[i];
for (int j = 0; j < m; ++j) cin >> gems[j];
// 将矿工能力与宝石硬度从小到大排序
sort(miners.begin(), miners.end());
sort(gems.begin(), gems.end());
// 双指针匹配
int i = 0; // 矿工指针
int j = 0; // 宝石指针
int matched = 0; // 成功匹配的矿工数量
while (i < n && j < m) {
if (miners[i] >= gems[j]) {
// 当前矿工能开采当前宝石，匹配成功
++matched;
++i;
++j;
} else {
// 当前矿工能力不足，换下一个更强的矿工
++i;
}
}
cout << matched << "\n";
return 0;
}
Java：
import java.io.*;
import java.util.*;
/**
* 等价于给定的 Python 版本：
* 输入：
* n m
* n 个矿工能力
* m 个宝石硬度
* 输出：最大匹配数量
*/
public class Main {
// 快速输入
static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
int nextInt() throws IOException {
int c, s = 1, x = 0;
do { c = read(); } while (c <= ' '); // 跳过空白
if (c == '-') { s = -1; c = read(); }
while (c > ' ') {
x = x * 10 + (c - '0');
c = read();
}
return x * s;
}
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
int n = fs.nextInt();
int m = fs.nextInt();
int[] miners = new int[n];
int[] gems = new int[m];
for (int i = 0; i < n; i++) miners[i] = fs.nextInt();
for (int j = 0; j < m; j++) gems[j] = fs.nextInt();
// 将矿工能力与宝石硬度从小到大排序
Arrays.sort(miners);
Arrays.sort(gems);
// 双指针匹配
int i = 0; // 矿工指针
int j = 0; // 宝石指针
int matched = 0; // 成功匹配的矿工数量
while (i < n && j < m) {
if (miners[i] >= gems[j]) {
// 当前矿工能开采当前宝石，匹配成功
matched++;
i++;
j++;
} else {
// 当前矿工能力不足，换下一个更强的矿工
i++;
}
}
System.out.println(matched);
}
}
Python：
def solve(): """ 主函数，用于读取输入、处理数据并输出结果。 """ # 读取第一行：矿工数量 n 和宝石数量 m # input().split() 将输入的一行按空格分割成字符串列表 # map(int, ...) 将列表中的每个字符串转换为整数 n, m = map(int, input().split()) # 读取第二行：n 位矿工的挖掘能力 miners_ability = list(map(int, input().split())) # 读取第三行：m 颗宝石的硬度 gems_hardness = list(map(int, input().split())) # 将矿工能力和宝石硬度都从小到大排序 miners_ability.sort() gems_hardness.sort() # 初始化指针和计数器 miner_ptr = 0# 指向当前考虑的矿工 gem_ptr = 0 # 指向当前考虑的宝石 successful_miners = 0# 成功匹配的矿工数量 # 当矿工和宝石都还有剩余时进行循环 while miner_ptr < n and gem_ptr < m: # 如果当前矿工的能力足以开采当前宝石 if miners_ability[miner_ptr] >= gems_hardness[gem_ptr]: # 匹配成功 successful_miners += 1 # 考虑下一位矿工 miner_ptr += 1 # 考虑下一颗宝石（因为这颗已经被开采） gem_ptr += 1 else: # 当前矿工能力不足，无法开采这颗宝石 # 只能让能力更强的下一位矿工来尝试 miner_ptr += 1 # 输出最终结果 print(successful_miners) # 调用函数执行 solve()
第二题：循环节
给出两个正整数 p 和 q, 根据 p / q 的结果进行输出:若为有限小数则输出 "0".若为无线循环则输出 p / q 的循环节.若为无限不循环小数则输出 "Wow!".
输入描述
第一行为一个正整数 T, 表示有多少组数据
接下来 T 行, 每行包含两个正整数 (空格分隔), 前面的数字表示 p, 后面的数字表示 q
输出描述
T 行, 每行一个整数表示对应数据组的答案。
样例输入
4
1 4
2 3
5 6
8 7
样例输出
0
6
3
142857
说明：
1 / 4 = 0.25
2 / 3 = 0.666...
5 / 6 = 0.9333...
8 / 7 = 1.142857142857142857...
参考题解
判断有限小数： 一个分数 p/q 是有限小数的充要条件是，当分数化为最简形式时，分母 q 的质因数只有 2 和 5。我们可以通过不断将 q 除以 2 和 5，如果最后 q 变为 1，那么它就是有限小数。寻找循环节： 如果分数是无限循环小数，我们可以通过模拟长除法的过程来找到循环节。在长除法中，我们计算的是余数。首先，我们计算 p 除以 q 的整数部分，这部分不影响循环节。我们真正关心的是小数部分，它由 p % q 决定。我们用当前的余数 r 乘以 10，然后除以 q，得到小数位上的一位数字，同时产生一个新的余数。我们重复这个过程。当某一个余数在之前已经出现过时，就意味着循环开始了。从上一次出现该余数的位置到当前位置之间的所有小数位数字，就构成了循环节。我们可以用一个字典或哈希表来记录出现过的余数以及它们出现的位置。关于无限不循环小数： 有理数（两个整数相除的结果）的小数表示只可能是有限小数或无限循环小数。无限不循环小数是无理数（如 π, √2），在本题的设定下（输入为两个整数 p 和 q）不可能出现，所以不需要输出 "Wow!"。
C++：
#include <bits/stdc++.h>
using namespace std;
/*
* 按照给定 Python 代码的逻辑：
* 1) 有限小数判断：直接在 q 上去掉因子 2 和 5（不与 p 先约分）
* 2) 否则用长除法找循环节：记录余数首次出现的位置
* 输入：
* T
* 接着 T 行：p q
* 输出：
* 如果有限小数输出 "0"，否则输出循环节字符串
*/
static string find_repeating_cycle(long long p, long long q) {
// 有限小数判断：不先约分，直接在 q 上消去 2 和 5
long long temp_q = q;
while (temp_q % 2 == 0) temp_q /= 2;
while (temp_q % 5 == 0) temp_q /= 5;
if (temp_q == 1) return "0";
// 否则：找循环节
long long remainder = p % q;
if (remainder < 0) remainder += q; // 以防 p 为负
unordered_map<long long, int> seen; // 余数 -> 小数位索引
vector<char> digits; // 小数各位（字符形式）
while (remainder != 0 && !seen.count(remainder)) {
seen[remainder] = (int)digits.size();
remainder *= 10;
long long digit = remainder / q;
digits.push_back(char('0' + (int)digit));
remainder %= q;
if (remainder < 0) remainder += q;
}
if (remainder == 0) {
// 按照原代码的健壮性返回 "0"
return "0";
} else {
// 循环开始位置
int start = seen[remainder];
// 从 start 到末尾就是循环节
return string(digits.begin() + start, digits.end());
剩余60%内容，订阅专栏后可继续查看/也可单篇购买
2025打怪升级记录，大厂笔试合集 C++, Java, Python等多种语言做法集合指南
查看8道真题和解析