ToB企服应用市场:ToB评测及商务社交产业平台

标题: 携程2025秋招0919笔试详细解答C++ [打印本页]
作者: 梦见你的名字    时间: 2024-9-22 12:28
标题: 携程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)，表现矩阵巨细和限制步数。
思绪非常直白，先下再右再左右横跳，无论是下还是右都可以用等差数列求解，至于左右横跳只必要分奇偶
  1. //先往下走，再往右走，再左右横跳
  2. #include <iostream>
  3. using namespace std;
  4. #define ll long long
  5. void solve() {
  6.     int n, m, k;
  7.     cin >> n >> m >> k;
  8.     ll ans = 0;
  9.     //可以到达底部
  10.     if (k >= n - 1) {
  11.         ans = n * m / 2 * (n - 1) * 1ll;
  12.         k -= (n - 1);
  13.     }
  14.     else {
  15.         ans = k * m * (k + 1) / 2 * 1ll;
  16.         k = 0;
  17.     }
  18.     //可以走到最右侧
  19.     int last = (n - 1) * m;//最后一行第一个格子的宝藏
  20.     if (k >= m - 1) {
  21.         ans += (last + 1 + last + m - 1) * (m - 1) / 2 * 1ll;
  22.         k -= (m - 1);
  23.     }
  24.     else {
  25.         ans += (last + 1 + last + k) * k / 2 * 1ll;
  26.         k = 0;
  27.     }
  28.     //需要反复横跳
  29.     last = n * m - 1;//最后一行最后一个格子的宝藏
  30.     int pre = last - 1;//last的前一个格子
  31.     if (k > 0) {
  32.         //如果k是偶数，那么last和pre都可以被访问k/2次
  33.         if (k % 2 == 0) ans += k / 2 * (last + pre);
  34.         else ans += (k + 1) / 2 * pre + k / 2 * last;
  35.     }
  36.     cout << ans << endl;
  38. }
  40. int main() {
  41.     int t;
  42.     cin >> t;
  43.     while (t--) {
  44.         solve();
  45.     }
  46. }
复制代码
选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

eg：
输入：
5 3 2
5 4 4 2 1
{5, 4, 4, 2, 1}，排序后酿成 {1, 2, 4, 4, 5}

无语死了家人们，看不懂题做一天，看懂题三分钟
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  6. int main() {
  7.     int n, m, k;
  8.     cin >> n >> m >> k;
  9.     vector<int> a(n);
  11.     for (int i = 0; i < n; i++) {
  12.         cin >> a[i];
  13.     }
  15.     sort(a.begin(), a.end()); // 从小到大排序
  17.     int ans = n;
  18.     //维护一个定长数组
  19.     for (int i = 0; i <= a.size() - m; i ++) {
  20.         if (a[i + m - 1] - a[i] <= k) ans--;
  21.     }
  22.     cout << ans;
  23. }
复制代码
选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，合唱团的气力界说为合唱团中所有人的最小能力值、
你有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
  2. #include <iostream>
  3. #include <vector>
  4. #include <algorithm>
  5. using namespace std;
  6. int n, k, l;
  7. int res;
  8. bool check(vector<int>& b, int val) {
  9.         // 假设这个函数检查能否通过至多 k 次训练，让所有人的能力至少为 val
  10.         int need_trainings = 0;
  11.         int i = 0;
  12.         while (i < n) {
  13.                 if (b[i] < val) {
  14.                         need_trainings++;
  15.                         i += l;
  16.                 }
  17.                 else {
  18.                         i++;
  19.                 }
  20.         }
  21.         return need_trainings <= k;
  22. }
  23. int main() {
  24.         cin >> n >> k >> l;
  25.         vector<int> a(n, 0);
  26.         vector<int> b(n, 0);
  27.         for (int i = 0; i < n; i++) {
  28.                 cin >> a[i];
  29.                 b[i] = a[i];
  30.         }
  31.         sort(a.begin(), a.end());
  32.         int left = 0, right = a.size() - 1;
  33.         while (left <= right) {
  34.                 int mid = left + (right - left) / 2;
  35.                 if (check(b, a[mid])) {
  36.                         res = mid;//先保留这一版本的res
  37.                         left = mid + 1;
  38.                 }
  39.                 else {
  40.                         right = mid - 1;
  41.                 }
  42.         }
  43.         cout << a[res];
  44. }
复制代码
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。



欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4