计算网格内走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();
- }
- }
游游在黑板上写下了 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;
- }
游游有个 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
- #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];
- }
|
