题解
【基础】倒水
4 条题解
-
0
#include <bits/stdc++.h> using namespace std; int a[100005], d[100005]; int main(){ int n, k, l, r, p; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i];//输入原数组 d[i] = a[i] - a[i - 1];//计算差分数组 } //进行k次修改,往某个区间里的杯子倒水 while (k--) { cin >> l >> r >> p;//l~r区间的杯子里倒入p毫升的水 d[l] += p;//左端点相较于左边的数增加了 d[r + 1] -= p;//右端点+1的位置相较于左边变矮了 } //差分数组进行前缀和运算就能得到原数组 for (int i = 1; i <= n; i++) { d[i] += d[i - 1]; cout << d[i] << ' '; } return 0; } -
0
#include <bits/stdc++.h> using namespace std; /* 【解题思路】 这个题目其实就是“听指令做动作”。我们有两个杯子 a 和 b,手里拿着一张只有三条规则的清单: 1. 规则一:如果 1 号杯满了,就把它倒空(泼掉)。 2. 规则二:如果 1 号没满,但 2 号杯是空的,就把 2 号杯接满水。 3. 规则三:如果上面两个都不满足,就把 2 号杯的水往 1 号杯里倒,直到 1 号满了或者 2 号空了。 我们只要用一个循环,把这些动作重复做 k 次,最后看杯子里剩多少水就行了。 */ int main() { int a, b, k; // a, b 是杯子容量(上限),k 是操作次数 cin >> a >> b >> k; int a1 = 0, b1 = 0; // a1, b1 是杯子里现在的实际水量,刚开始都是空的 for (int i = 0; i < k; i++) { // 规则一:1 号杯满了吗? if (a1 == a) { a1 = 0; // 倒掉,变空 } // 规则二:2 号杯空了吗? else if (b1 == 0) { b1 = b; // 接满水 } // 规则三:互相倒水 else { // 看看 2 号杯剩下的水,够不够把 1 号杯填满 if (a1 + b1 >= a) { // 如果够填满:把 1 号杯差的那点水(a - a1)从 2 号里减掉 b1 -= (a - a1); a1 = a; // 1 号杯现在满了 } else { // 如果不够填满:把 2 号杯的水全部给 1 号 a1 = a1 + b1; b1 = 0; // 2 号杯空了 } } } cout << a1 << " " << b1; return 0; } -
0
#include <bits/stdc++.h> using namespace std; int a[100005], d[100005]; int main(){ int n, k, l, r, p; cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } //计算差分数组,差分用于区间修改比较方便 for (int i = 1; i <= n; i++) { d[i] = a[i] - a[i - 1]; } //进行k次修改, 针对差分数组有变动的地方进行改动 while (k--) { cin >> l >> r >> p; d[l] += p; d[r + 1] -= p; } //对差分数组进行前缀和运算并输出 //差分数组前缀和运算后可以得到原数组 for (int i = 1; i <= n; i++) { d[i] += d[i - 1]; cout << d[i] << ' '; } return 0; }
- 1