查询域名官网的是那个网站吗,qq空间电脑版,建站工具有哪些论坛,外贸网站建设980描述
在一个桌子上摆放了n个杯子#xff0c;每个杯子中有一定量的水。小A同学负责向杯子中倒水#xff0c;他总共倒了k次#xff0c;每次会向从第L个杯子到第R个杯子中添加P毫升的水#xff08;注意#xff1a;水只可能增加#xff0c;不可能减少#xff09;。 请问小A…描述
在一个桌子上摆放了n个杯子每个杯子中有一定量的水。小A同学负责向杯子中倒水他总共倒了k次每次会向从第L个杯子到第R个杯子中添加P毫升的水注意水只可能增加不可能减少。 请问小A同学倒了k次水之后n个杯子每个杯子有多少毫升的水。
输入描述
第一行包含两个整数n和k。 第二行包含n个整数表示一开始每个杯子中水的毫升数。 接下来k行每行包含三个整数LRP表示一次操作。
输出描述
共一行包含n个整数表示最终n个杯子每个杯子有多少毫升的水。
用例输入 1
8 3
1 2 10 8 1 5 1 1
7 8 12
1 8 4
2 3 12
用例输出 1
5 18 26 12 5 9 17 17
提示
【数据范围】 1≤n,k≤100000, 1≤L≤R≤n, 0≤P≤1000, 0≤杯子中水的初始量≤1000
来源
前缀和差分
解析 初始化首先定义了两个数组a和b其中a数组用于存储每个杯子最初的水量b数组用于记录每次倒水后的水量变化。b[i]的值表示从第1个杯子到第i个杯子之间总共增加的水量。 输入从输入中读取杯子的数量n和倒水的次数m然后读取每个杯子最初的水量到a数组中。 计算初始水量变化通过a数组计算b数组b[i]存储的是第i个杯子相对于第i-1个杯子多出的水量。这里假设第0个杯子的水量为0因此b[1]即为第一个杯子的水量。 倒水操作对于每次倒水操作读取倒水的范围l和r以及水量p。在b数组的l位置加上p表示从第l个杯子开始增加水量在r1位置减去p表示在第r个杯子之后的水量要减去p确保水量只在l到r之间增加。 计算最终水量遍历b数组累加水量变化得到每个杯子最终的水量。这里通过累加操作将水量变化从b[1]到b[n]依次累加起来最终b[i]存储的就是第i个杯子最终的水量。 输出输出每个杯子最终的水量。
代码
#includeiostream
using namespace std; // 定义常量N表示数组的最大长度
const int N 100007; // 定义全局变量
int n, m, l, r, p; // n表示杯子数量m表示倒水的次数l和r表示倒水的范围p表示每次倒水的量
int a[N], b[N]; // a数组存储每个杯子最初的水量b数组用于记录每次倒水后的水量变化 int main() { // 输入杯子数量n和倒水次数m cin n m; // 初始化a数组存储每个杯子最初的水量 for(int i 1; i n; i) { cin a[i]; // 计算b数组b[i]表示第i个杯子相对于第i-1个杯子多出的水量 // 注意a[0]未定义这里假设a[0]为0即第0个杯子水量为0 b[i] a[i] - a[i - 1]; } // 执行m次倒水操作 for(int i 1; i m; i) { // 输入每次倒水的范围l, r和水量p cin l r p; // 在b数组对应位置加上p表示增加的水量 // l位置加上p表示从第l个杯子开始增加水量 b[l] p; // r1位置减去p表示在第r个杯子之后的水量要减去p // 这样可以确保在r位置结束增加水量 b[r 1] - p; } // 累加b数组得到每个杯子最终的水量 // b[i]存储的是从第1个杯子到第i个杯子总共增加的水量 for(int i 1; i n; i) { // 计算每个杯子最终的水量b[i]加上前一个杯子的水量b[i-1] b[i] b[i] b[i - 1]; // 输出每个杯子最终的水量 cout b[i] ; } return 0;
}
