携程2025秋招0919笔试详细解答C++
计算网格内走k步获取的最大价值
一个 n x m 的网格图 a，左上角为(0,0)，右下角为(n-1,m-1)，格子 (i,j) 价值为 i * m + j。
游游从左上角 (0,0) 为起点，每一步可以走到上下左右四个方向的相邻格子。
每到达一个格子，就能获取相应格子的奖励。
需要注意的是，在到达某个格子获取宝物后，这个格子的宝物会在游游离开格子后再次刷新。
现在给出一个整数 k，表示游游最多走 k 步。问:游游最多能获得多少价值的宝物?
输入：
第一行输入 q(1 <= q <= 10 ^ 5)，表示询问个数。
接下来 q 行，每行输入 n，m，k (1 <= n, m, k <= 10^4, n + m > 2)，表示矩阵大小和限制步数。
思路非常直白，先下再右再左右横跳，无论是下还是右都可以用等差数列求解，至于左右横跳只需要分奇偶
//先往下走，再往右走，再左右横跳
#include <iostream>
using namespace std;
#define ll long long
void solve() {
int n, m, k;
cin >> n >> m >> k;
ll ans = 0;
//可以到达底部
if (k >= n - 1) {
ans = n * m / 2 * (n - 1) * 1ll;
k -= (n - 1);
}
else {
ans = k * m * (k + 1) / 2 * 1ll;
k = 0;
}
//可以走到最右侧
int last = (n - 1) * m;//最后一行第一个格子的宝藏
if (k >= m - 1) {
ans += (last + 1 + last + m - 1) * (m - 1) / 2 * 1ll;
k -= (m - 1);
}
else {
ans += (last + 1 + last + k) * k / 2 * 1ll;
k = 0;
}
//需要反复横跳
last = n * m - 1;//最后一行最后一个格子的宝藏
int pre = last - 1;//last的前一个格子
if (k > 0) {
//如果k是偶数，那么last和pre都可以被访问k/2次
if (k % 2 == 0) ans += k / 2 * (last + pre);
else ans += (k + 1) / 2 * pre + k / 2 * last;
}
cout << ans << endl;
}
int main() {
int t;
cin >> t;
while (t--) {
solve();
}
}
选m个极差不超过k的数消掉最小的数，求剩余最少的数字数量
游游在黑板上写下了 n 个数字，构成了一个可重集合。
游游请你参与一个游戏 :
每轮操作你可以任选集合中**最大值和最小值的差不超过 k **的 m 个数字，
然后删去这 m 个数字中的最小值（删除一个），
并把其他的数字放回集合中。
若无法选出符合条件的m个数，则无法继续操作。
你可以无限次进行这个操作，直到没法操作为止。
要使得最后留下的数最少，请你求出操作后留下的最少的数字数量。
输入：
第一行三个整数n，m，k (2 <= m <= 106, 0 <= k <= 109)
第二行输入n个整数
输入：
4 3 3
1 2 3 6
输出：
3
题目看几遍都没看懂
看懂之后感觉自己很傻逼
每轮操作你可以任选集合中最大值和最小值的差不超过 k 的 m 个数字
这段话咱像分析英语句子一样给他拆开，形容词给他不要了
每轮操作你可以任选集合中最大值和最小值的差不超过 k 的 m 个数字
什么意思？让你维护一个长度为m的数组啊！
eg：
输入：
4 3 3
1 2 3 6
n = 4，m = 3，k = 3，有4个数，每次操作选3个，最大值和最小值的差不超过3
- {1，2，3}它们的最大值和最小值之差是 3 - 1 = 2，符合条件。删掉1，剩下{2, 3, 6}
- {2, 3, 6}，无法再选择出符合条件的 3 个数字（因为 6 - 2 = 4，超过 k = 3），游戏结束。
eg：
输入：
5 3 2
5 4 4 2 1
{5, 4, 4, 2, 1}，排序后变成 {1, 2, 4, 4, 5}
- {1, 2, 4}，最大值与最小值的差是 4 - 1 = 3，不符合条件。
- {2, 4, 4}，最大值与最小值的差是 4 - 2 = 2，符合条件。删掉 2，剩下 {4, 4, 5}。
- {4, 4, 5}，最大值与最小值的差是 5 - 4 = 1，符合条件。删掉 4，剩下 {4, 5}。游戏结束。最后是{1，4，5}，答案3。
无语死了家人们，看不懂题做一天，看懂题三分钟
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
sort(a.begin(), a.end()); // 从小到大排序
int ans = n;
//维护一个定长数组
for (int i = 0; i <= a.size() - m; i ++) {
if (a[i + m - 1] - a[i] <= k) ans--;
}
cout << ans;
}
选k个长度不超过l的区间改变数字，求最后剩余的最小数字
游游有个 n 人组成的合唱团，第 i 个人的能力值为 ai 。现在将 n 个人排成一排，游游有 k 次训练的机会，让不超过 l 个连续的人能力人变为任意值。如果合唱团的实力是所有人能力值的最小值。你可以帮助游游求出合唱团的实力的最大值是多少吗?
输入描述：
第一行三个整数n，k，l，表示人数，训练次数，每次训练的最大长度。(2 <= n <= 10^5, 1 <= k * l < n) 第二行n个整数ai，表示第i个人的能力值为ai(1 <= ai <= 1e9)
背景：
合唱团n个人，每个人能力值a[i]，合唱团的实力定义为合唱团中所有人的最小能力值、
你有k次训练机会，每次可以改变连续l个人的能力值，改变之后可以是任意值，你希望合唱团整体实力尽可能高。
目标：
通过k次训练，让合唱团的最小能力值尽可能地大
思路：
先排序一个a，保留原始数组b
在排过序的数组a中二分法找中间值，当做可能答案一个个试
假设当前mid就是最终的最小数，用check函数去判断，能不能以原数组为基础，将所有小于当前mid值的元素都提高
如果可以，先保留res，增加mid，即left+1
如果不能，就减小mid，即right-1
至于check函数，起始位置i，一个个试，
当前i值小于参数传递来的val，说明需要训练，标记训练++，i跳l个位置
当前i值大于参数传递来的val，说明不需要训练，i++
把所有元素试完，最后返回训练次数小于等于k
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, k, l;
int res;
bool check(vector<int>& b, int val) {
// 假设这个函数检查能否通过至多 k 次训练，让所有人的能力至少为 val
int need_trainings = 0;
int i = 0;
while (i < n) {
if (b[i] < val) {
need_trainings++;
i += l;
}
else {
i++;
}
}
return need_trainings <= k;
}
int main() {
cin >> n >> k >> l;
vector<int> a(n, 0);
vector<int> b(n, 0);
for (int i = 0; i < n; i++) {
cin >> a[i];
b[i] = a[i];
}
sort(a.begin(), a.end());
int left = 0, right = a.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(b, a[mid])) {
res = mid;//先保留这一版本的res
left = mid + 1;
}
else {
right = mid - 1;
}
}
cout << a[res];
}
原文地址：https://blog.csdn.net/weixin_45962681/article/details/142384075
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！