csp 202203-2 出行计划

csp 202203-2 出行计划

问题描述
最近西西艾弗岛上出入各个场所都要持有一定时限内的核酸检测阴性证明。

具体来时，如果在 时刻做了核酸检测，则经过一段时间后可以得到核酸检测阴性证明。这里我们假定等待核酸检测结果需要 个单位时间，即在 时刻可以获得结果。如果一个场所要求持 个单位时间内核酸检测结果入内，那么凭上述的核酸检测结果，可以在第 时刻到第 时刻进入该场所。

小 C 按时间顺序列出接下来的 项出行计划，其中第 项（）可以概括为：
时刻进入某场所，该场所需持有 个单位时间内的核酸检测结果入内，其中 。

为了合理安排核酸检测时间，试根据小 C 的出行计划，回答如下查询：

如果在 时刻做了核酸检测，有多少项出行计划的核酸检测要求可以得到满足？
这样的查询共有 个，分别为 ；查询之间互不影响。

输入格式
输入的第一行包含空格分隔的三个正整数 、 和 ，分别表示出行计划数目、查询个数以及等待核酸检测结果所需时间。

接下来输入 行，其中每行包含用空格分隔的两个正整数 、，表示一项出行计划；出行计划按时间顺序给出，满足 。

最后输入 行，每行仅包含一个正整数 ，表示一个查询。 个查询亦按照时间顺序给出，满足 。

输出格式
输出共 行，每行一个整数，表示对应查询的答案。

样例输入

6 2 10
5 24
10 24
11 24
34 24
35 24
35 48
1
2
1
2
3
4
5
6
7
8
9

Data
样例输出

3
3
1
2

Data
样例解释
时刻 做检测，可以满足第三、四、六项出行计划；

时刻 做检测，可以满足第四、五、六项出行计划。

解决方法——查分数组

1.什么是差分数组？
从字面上解释，差分数组就是记录一个数组的前后元素之差的数组，例如：

有数组nums的内容如下：

0	1	2	3	4	5
2	4	1	5	8	10
1
2

那么数组nums的差分数组diff就是：

        0	1	2	3	4	5
nums	2	4	1	5	8	10
diff	2	2	-3	4	3	2
1
2
3

数组diff的长度和原数组nums一样，其中diff[0]默认为nums[0]，其它diff[i] = nums[i] - nums[i-1]。

（1）差分数组的特点一：

当我们需要在长度很大的原数组的某个区间做频繁的统一运算操作时，可以不操作原数组，而是直接计算其差分数组以提高效率。举个简单的例子，现在需要将上面数组nums的[1, 3]区间元素都累加2，则结果如下：

        0	1	2	3	4	5
nums	2	4+2	1+2	5+2	8	10
diff	2	2+2	-3	4	3+(-2)	2
1
2
3

所以对原数组某个区间的操作只会影响差分数组中两个元素的值，如果区间是[i,j]，那么只会影响差分数组的i和j+1两个元素

（2）差分数组的特点二：

d[i] = f[0] + f[1] + … + f[i]

即用差分数组的前i项和可以求得原数组的第i个元素的值！

nums[3] = 7 = diff[0] + diff[1] + diff[2] + diff[3] = 2 + 4 - 3 + 4 = 7

代码

#include 
#include 

using namespace std;
int main(){
	int a[400100] = {0};
	int first,second;
	int num1,num2,waitTime;
	cin >> num1>>num2>>waitTime;
	for(int i = 0;i<num1;i++){
		cin>>first>>second;
		if(first - second < 0 ){
			a[0]++;
			a[first+1]--;
		}else{
			a[first-second+1]++;
			a[first +1]--;
		}
	}
	for(int i = 1; i <400090;i++){
		a[i] = a[i]+a[i-1];
	}
	for(int i = 0;i<num2;i++){
		cin>>first;
		cout<<a[first+waitTime]<<endl;
	}
	return 0;
} ```


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30