atcoder解题
#include <iostream>
#include <vector>using namespace std;int main() {long long N, M;cin >> N >> M;vector<long long> X(M), A(M);long long totalStones = 0;// 读入 X 和 Afor (int i = 0; i < M; i++) {cin >> X[i];}for (int i = 0; i < M; i++) {cin >> A[i];totalStones += A[i]; // 计算总石头数}// 如果总石头数不等于 N，输出 -1if (totalStones != N) {cout << -1 << endl;return 0;}long long moves = 0; // 操作次数long long currentStones = 0; // 当前单元格的石头数量// 使用一个数组来表示每个位置的石头数量vector<long long> stones(N, 0);for (int i = 0; i < M; i++) {stones[X[i]] = A[i];}// 从左到右遍历for (int i = 0; i < N - 1; i++) {currentStones += stones[i]; // 当前单元格的石头数if (currentStones > 1) {moves += currentStones - 1; // 多余的石头移到下一个单元格currentStones = 1; // 当前单元格只剩 1 块石头} else if (currentStones < 1) {moves += 1 - currentStones; // 缺少的石头移动到当前单元格currentStones = 1; // 当前单元格补齐}}// 输出最少的移动次数cout << moves << endl;return 0;
}
详细解释各段
vector<long long> X(M), A(M);
long long totalStones = 0;
X数组存储每个含有石头的单元格的位置（从 0 到 N−1）。A数组存储每个含有石头的单元格上有多少块石头。totalStones用来计算所有石头的总数。
// 从左到右遍历
for (int i = 0; i < N - 1; i++) {currentStones += stones[i]; // 当前单元格的石头数if (currentStones > 1) {moves += currentStones - 1; // 多余的石头移到下一个单元格currentStones = 1; // 当前单元格只剩 1 块石头} else if (currentStones < 1) {moves += 1 - currentStones; // 缺少的石头移动到当前单元格currentStones = 1; // 当前单元格补齐}
}
解释：
-
从左到右遍历：我们从左到右逐个遍历每个单元格（从 0 到 N−1，但最后一个单元格 N−1 没有后续单元格可以接收石头，所以我们遍历到 N−2）。
-
currentStones += stones[i]：currentStones累加当前单元格 i 上的石头数量。- 这样
currentStones记录的是从左侧到当前单元格的石头总数。
-
处理多余石头的情况：
- 如果
currentStones > 1，说明当前单元格的石头数量超过 1 块。为了让当前单元格恰好有 1 块石头，我们需要将多余的石头移动到右边的单元格。 - 移动的石头数是
currentStones - 1，因此我们将移动次数moves增加currentStones - 1。 - 然后将
currentStones设置为 1，表示当前单元格的石头数量已经调整为 1。
- 如果
-
处理缺少石头的情况：
- 如果
currentStones < 1，说明当前单元格缺少石头。为了让当前单元格恰好有 1 块石头，我们需要从左边的单元格（或前面已经移动过来的石头）补充石头。 - 需要移动的石头数是
1 - currentStones，所以我们将moves增加1 - currentStones。 - 然后将
currentStones设置为 1，表示当前单元格的石头数量已经补齐为 1。
- 如果
但是stones 数组分配了大小为 N 的数组，然而，题目给出的约束条件中 N 最大可以达到 2×10九次方，这意味着直接分配大小为 N 的数组可能会导致内存溢出，程序崩溃。
即使我们可以分配内存，处理的时间复杂度可能会非常高，尤其是当 N 非常大的时候。
代码修改：
- 使用一个哈希映射（map）存储石头的位置信息，不再创建大小为 N 的数组。只需要存储那些含有石头的单元格的位置和对应的石头数量。
- 使用一个变量
currentStones来跟踪当前单元格的石头数量，而不是遍历所有单元格。
修改后的代码如下：
#include <iostream>
#include <vector>
#include <map>using namespace std;int main() {long long N, M;cin >> N >> M;vector<long long> X(M), A(M);long long totalStones = 0;// 读入 X 和 Afor (int i = 0; i < M; i++) {cin >> X[i];}for (int i = 0; i < M; i++) {cin >> A[i];totalStones += A[i]; // 计算总石头数}// 如果总石头数不等于 N，输出 -1if (totalStones != N) {cout << -1 << endl;return 0;}long long moves = 0; // 操作次数long long currentStones = 0; // 当前单元格的石头数量// 使用一个 map 来表示每个含有石头的单元格位置和石头数量map<long long, long long> stones;for (int i = 0; i < M; i++) {stones[X[i]] = A[i];}// 从左到右遍历for (long long i = 0; i < N - 1; i++) {// 如果当前单元格有石头if (stones.count(i) > 0) {currentStones += stones[i]; // 当前单元格的石头数}if (currentStones > 1) {moves += currentStones - 1; // 多余的石头移到下一个单元格currentStones = 1; // 当前单元格只剩 1 块石头} else if (currentStones < 1) {moves += 1 - currentStones; // 缺少的石头移动到当前单元格currentStones = 1; // 当前单元格补齐}}// 输出最少的移动次数cout << moves << endl;return 0;
}
主要改动
- 使用
map<long long, long long> stones:- 我们用
map来存储每个含有石头的单元格的位置及其石头数量。这样就可以有效避免为所有单元格分配内存，只有 M 个含石头的单元格需要存储。 stones.count(i)用来检查当前单元格 iii 是否有石头。如果有石头，就将该位置的石头数量加到currentStones中。
- 我们用
- 避免遍历所有单元格：
- 我们仍然从左到右遍历所有单元格（从 0 到 N−2），但是不再维护一个大小为 N 的数组来表示每个单元格的石头数量，而是通过
map来动态获取每个含石头单元格的数量。
- 我们仍然从左到右遍历所有单元格（从 0 到 N−2），但是不再维护一个大小为 N 的数组来表示每个单元格的石头数量，而是通过