AcWing 797. 差分
原题链接
简单
作者:
MeowRain
,
2024-01-09 20:09:16
,
所有人可见
,
阅读 32
#include <iostream>
#include <cassert>
const int N = 1e5;
int nums[N];
class Difference {
private:
int* diff; // 差分数组指针
int length; // 数组长度
public:
// 构造函数,初始化差分数组
Difference(int* nums, int length) {
assert(length > 0); // 确保数组长度大于0
diff = new int[length](); // 分配长度为length的int型动态数组,初始化为0
this->length = length; // 保存数组长度
diff[0] = nums[0]; // 第一个元素直接赋值为nums的第一个元素
// 计算差分数组
for (int i = 1; i < length; i++) {
diff[i] = nums[i] - nums[i - 1];
}
}
// 获取差分数组的指针
int* getDiffArray() {
return this->diff;
}
// 执行区间增量操作
void increment(int i, int j, int c) {
diff[i] += c; // 在i处增加c
diff[j + 1] -= c; // 在j+1处减少c(通过差分数组实现)
}
// 计算最终结果数组
int* result() {
int* res = new int[length](); // 创建长度为length的int型动态数组
res[0] = diff[0]; // 直接赋值第一个元素
// 根据差分数组计算结果数组
for (int i = 1; i < length; i++) {
res[i] = res[i - 1] + diff[i];
}
return res; // 返回结果数组的指针
}
// 析构函数,释放动态分配的内存
~Difference() {
delete[] diff; // 释放差分数组的内存
}
};
int main(void) {
int n, m;
std::cin >> n >> m; // 输入n和m
for (int i = 0; i < n; i++) {
std::cin >> nums[i]; // 输入数组nums
}
Difference dif(nums, n); // 创建Difference对象dif,并传入数组和数组长度
// 执行m次区间增量操作
for (int k = 0; k < m; k++) {
int i, j, c;
std::cin >> i >> j >> c; // 输入i、j和c
i -= 1; // 调整i和j的值
j -= 1;
dif.increment(i, j, c); // 执行区间增量操作
}
int* res = dif.result(); // 获取结果数组指针
// 输出结果数组
for (int i = 0; i < n; i++) {
std::cout << res[i] << " ";
}
delete[] res; // 释放结果数组的内存
res = nullptr; // 将指针置为空指针
return 0;
}