题目描述
题目大意
给定正整数 \(n, m\)，求一个矩阵 \(A\) 满足：
- 矩阵的每一行 \(A_i = (A_{i, 1}, \ldots, A_{i, m})\)（\(1 \le i \le n\)）均为 \(1 \sim m\) 的排列
- 按题面所示的移动方式使得路径上的数字之和最小。
- 在该移动方式中，就是在同一行、当前位置往左数 \(k_x\) 个、往右数 \(k_x\) 个之间的位置中，找到数值最大的位置并瞬移再向下移动一格。初始位置为 \((1, 1)\)。
思路
本题主要考察：贪心。
在该移动方式中，就是在同一行、当前位置往左数 \(k_x\) 个、往右数 \(k_x\) 个之间的位置中，找到数值最大的位置并瞬移再向下移动一格。
从上一行移动下来的位置的数字必定为1。
那么若当前位置往左数 \(k_x\) 个、往右数 \(k_x\) 个之间的位置中并不会超越边界，必定是将 \(1 \sim m\) 中小的数放在这些位置上。
所以，如果可以瞬移到的位置固定，那么答案也将固定，将取决于可以瞬移到的位置的个数。
因此，想要使得路径上的数字之和最小，就要利用边界减小可以瞬移到的位置的个数。
至此，贪心策略就显而易见了：
每一行初始的位置（从上一行下来的位置）的数字为1，之后瞬移的位置尽量选择靠近左边界或右边界。若无法瞬移至左边界或右边界，那就选择距离左边界或右边界1格的位置。
具体细节见代码注释。
代码
#include <bits/stdc++.h>
using namespace std;typedef long long LL;
typedef unsigned int UINT;
typedef unsigned long long ULL;typedef pair<int, int> PII;
typedef pair<LL, LL> PLL;
#define x first
#define y secondconst int N = 5e5 + 5;
int n, m;
int a[N];signed main()
{scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++ )scanf("%d", &a[i]);LL res = 0; // res 储存答案bool flag = true; // flag 表示 当前位置是否为左边界或右边界for (int i = 1; i <= n; i ++ ){res ++ ; // 从上一行下来的位置的数字为1，记录答案if (flag) // 若当前位置是边界{res += min(a[i], m - 1) + 1; // min(a[i], m - 1) + 1 为 可以瞬移到的位置的个数if (a[i] >= m - 1) flag = true; // 如果当前位置可以瞬移至边界，那么就瞬移至边界else flag = false; // 否则，瞬移至与边界的距离为1的位置}else // 若当前位置与边界的距离为1{res += min(a[i], m - 2) + 2; // min(a[i], m - 2) + 2 为 可以瞬移到的位置的个数flag = true; // 因为 a[i]>= 1，所以当前位置必定可以瞬移至边界}}printf("%lld\n", res); // 输出答案return 0; // 完结撒花
}