202203-2-出行计划 - csp - 计算机科学 | Mi Manchi = yuan = Whatever is worth doing at all is worth doing well

# 题目

1661843616234

能否出行决定于出行时间是否落到核酸检测证明有效的时间区间内。

输入格式中的 $t_i$ 为出行时间， $q_i$ 为区间长度， $q_i + k$ 为区间的左端点。

如果直接做，则需要事先存储全部的出行计划，而后遍历每个出行计划，得到时间区间后判断出行时间是否在时间区间之内。（每个出行计划的出行时间和区间长度都可能是不一样的），时间复杂度为 $n \times m$

在不等式中有三个变量，在上面的理解中是以出行时间作为中心变量，判断其是否合适。结合输入输出的特点，将中心变量转换为做核酸的时间。

最终的时间复杂度为 $max(m, n)$

	#include <iostream>
	#include <map>
	#include <vector>

	//#define aaa

	using namespace std;

	/*
	* 输入 t 和 c、q，在 t 时刻进入场所，在 q 时刻做核酸
	*
	* t 的取值范围是 [q+k, q+k+c-1] 这里及下面都是闭区间
	* 变换后得 q 的范围是 [t-k-c+1, t-k]
	*
	* 建立的数组的下标表示 q 的取值，该位置的数组的值表示 q 在该取值下能进行的出行活动个数
	*
	* 因此在获得每对 t 和 c 后，在 [t-k-c+1, t-k] 上每个位置加 1，表示 q 取这些值时这个活动可以进行，活动个数加 1
	*
	* 利用差分数组，即在 [t-k-c+1] 位置处加 1，[t-k+1] 位置处减 1
	*/

	vector<pair<int, int> > ve;
	int n, m, k;

	int d[200005];
	int s[200005];

	int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	#ifdef aaa
	freopen("stdin.txt", "r", stdin);
	#endif

	cin >> n >> m >> k;

	for (int i = 0; i < n; i++) {
	int t, c;
	cin >> t >> c;
	int st = t - k - c + 1;
	int ed = t - k + 1;

	if (ed <= 0)
	continue;

	st = max(st, 1);
	d[st] += 1;
	d[ed] -= 1;

	}

	for (int i = 1; i < 200005; i++) {
	s[i] = s[i - 1] + d[i];
	}

	for (int i = 0; i < m; i++) {
	int q;
	cin >> q;

	cout << s[q] << endl;
	}
	}