标签：ch CSP202203 int 场所 while getchar

CSP202203_2

目录

• CSP202203_2
  • 题目
  • 思路
    • 暴力
    • 差分
  • Code

题目

出行计划

思路

暴力

针对每一次的 q 询问，遍历所有场所判断是否可行。由于场所的计划到达时间 t 升序给出，因此可以倒序遍历场所。针对核酸生效时间 q + k，如果计划晚到达的场所都不满足，要求更早到达的场所也一定不可行。

总体还是\(O(mn)\)，70pts。

差分

考虑判断哪些 q 可以满足某一场所的访问时间。

针对任意场所，核酸生效时间为 q + k，其要求持有 c 时间内的核酸证明。因此对于 t 时间到达该场所的要求，应满足：

\[q + k \leq t \leq q + k + c - 1 \]

而转化为对 q + k 的要求，即可得到：

\[t + 1 - c\leq q + k \leq t - k \]

因此使用差分维护，在 \(q + k \in [t + 1 - c, t - k]\)时，可访问的场所数加一。

最后使用前缀和，pre[i] 即为 q + k 为 i 时，所有可访问地点的总数。

Code

1. 暴力(70pts)

   #include<bits/stdc++.h>
   
   using namespace std;
   
   inline int read()
   {
   	int x = 0, f = 1;
   	char ch = getchar();
   	while(ch < '0' || ch > '9')
   	{
   		if(ch == '-') f = -1;
   		ch = getchar();
   	}
   	while(ch >= '0' && ch <= '9')
   	{
   		x = (x<<1) + (x<<3) + (ch^48);
   		ch = getchar();
   	}
   	return x*f;
   }
   
   int n, m, k;
   int t[100010], c[100010];
   
   int main()
   {
   	n = read(), m = read(), k = read();
   	for(int i = 1; i <= n; i++)
   	{
   		t[i] = read();
   		c[i] = read();
   	}
   	for(int i = 1; i <= m; i++)
   	{
   		int q = read();
   		q += k;
   		int ans = 0;
   		for(int j = n; j >= 1; j--)
   		{
   			if(t[j] >= q && t[j] <= q + c[j] - 1)
   			{
   				ans++;
   			}
   			else
   			{
   				if(t[j] < q)
   				{
   					break;
   				}
   			}
   		}
   		cout << ans << endl;
   	}
   	return 0;
   }
   /*
   6 2 10
   5 24
   10 24
   11 24
   34 24
   35 24
   35 48
   1
   20
   */
   

2. 差分(100pts)

   #include<bits/stdc++.h>
   
   using namespace std;
   
   inline int read()
   {
   	int x = 0, f = 1;
   	char ch = getchar();
   	while(ch < '0' || ch > '9')
   	{
   		if(ch == '-') f = -1;
   		ch = getchar();
   	}
   	while(ch >= '0' && ch <= '9')
   	{
   		x = (x<<1) + (x<<3) + (ch^48);
   		ch = getchar();
   	}
   	return x*f;
   }
   
   int n, m, k;
   
   int dif[300010];
   int pre[300010];
   
   int main()
   {
   	n = read(), m = read(), k = read();
   	for(int i = 1; i <= n; i++)
   	{
   		int t = read(), c = read();
   		int l = ( t + 1 - c >= 1 ? t + 1 - c : 1);
   		int r = t;
   		dif[l] += 1;
   		dif[r + 1] -= 1;
   	}
   	for(int i = 1; i < 300010; i++)
   	{
   		pre[i] = pre[i - 1] + dif[i];
   	}
   	for(int i = 1; i <= m; i++)
   	{
   		int q = read();
   		q += k;
   		cout << pre[q] << endl;
   	}
   	return 0;
   }
   /*
   6 2 10
   5 24
   10 24
   11 24
   34 24
   35 24
   35 48
   1
   20
   */
   

标签：ch,CSP202203,int,场所,while,getchar
From： https://www.cnblogs.com/kevin-chance/p/16725406.html