Greg and Array CodeForces 296C 差分数组

题意

是说有n个数，m种操作，这m种操作就是让一段区间内的数增加或则减少，然后有k种控制，这k种控制是说让m种操作中的一段区域内的操作来实际进行，问进行完k种控制后，这n个数变成了啥。

解题思路

我开始使用了最简单的差分，就是把m种操作存到结构体数组中，然后在读取k中控制时，按照要求执行之前结构体数组中的一段区间内的操作，但是这样超时了。后来一想，如果直接知道m种操作每种操作的次数不就行了，于是我们需要两个数组，一个是用来记录m种操作它们需要进行的次数，另一个就是原来数组中的值。

详细看代码实现

代码实现

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int maxn=1e5+7;

struct node{

	ll l, r, x;

}op[maxn];

ll num[maxn], ca[maxn];//这个存储原数组值的差分

ll qujian[maxn]; //存储每种操作的次数

int n, m, k;

int main()

{

	cin>>n>>m>>k;//注意这里一定要用cin和cout来进行输入输出，题目要求

	for(int i=1; i<=n; i++)

	{

		cin>>num[i];

		ca[i]=num[i]-num[i-1];

	}

	for(int i=1; i<=m; i++)

	{

		cin>>op[i].l>>op[i].r>>op[i].x;//把m中操作按照顺序存到结构体数组中

	}

	ll x, y;

	for(int i=1; i<=k; i++)

	{

		cin>>x>>y;

		qujian[x]++;

		qujian[y+1]--;

	}

	ll tmp=0;

	for(int i=1; i<=m; i++)

	{

		tmp+=qujian[i];

		ca[op[i].l]+=tmp*op[i].x;

		ca[op[i].r+1]-=tmp*op[i].x;

	}

	tmp=0;

	for(int i=1; i<=n; i++)

	{

		tmp+=ca[i];

		cout<<tmp<<" ";

	}

	cout<<endl;

	return 0;

}

巴特西

Greg and Array CodeForces 296C 差分数组

Greg and Array CodeForces 296C 差分数组

题意

解题思路

代码实现

最新文章

热门文章