补题 [CF1840C] Ski Resort

题目描述

Dima Vatrushin 是一所学校的数学教师。由于他的出色工作，他被派去度假 $n$ 天。Dima长期以来一直梦想去滑雪胜地，因此他想安排几天连续的时间去滑雪。由于度假需要仔细准备，他至少要去 $k$ 天。

给定一个包含度假胜地天气预报的数组 $a$。换句话说，在第 $i$ 天，气温将为 $a_i$ 度。

Dima出生在西伯利亚，因此只有整个假期都不超过 $q$ 度的情况下，他才能度假。

不幸的是，Dima学数学学的，以至于他忘记了如何计算。他请求你帮助他计算在胜地选择度假日的方法数。

输入格式

输入的第一行包含一个整数 $ t $ ( $ 1 \le t \le 10^4 $ ) — 表示测试用例的数量。

接下来是每个测试用例的描述。

每个测试用例的第一行包含三个整数 $ n $ , $ k $ , $ q $ ( $ 1 \le n \le 2 \cdot 10^5 $ , $ 1 \le k \le n $ , $ -10^9 \le q \le 10^9 $ )— 数组 $ a $ 的长度，Dima 在度假村最少需要的天数，以及他能接受的最高温度。

每个测试用例的第二行包含 $ n $ 个整数 $ a_1, a_2, a_3, \dots, a_n $ ( $ -10^9 \le a_i \le 10^9 $ ) — 滑雪度假村的温度。

所有测试用例中 $n$ 的总和不超过 $ 2 \cdot 10^5 $。

输出格式

输出 $ t $ 个整数，每个对应于一个测试用例的答案，表示 Dima 在度假村选择度假日期的方法数。

样例 #1

样例输入 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
7
3 1 15
-5 0 -10
5 3 -33
8 12 9 0 5
4 3 12
12 12 10 15
4 1 -5
0 -1 2 5
5 5 0
3 -1 4 -5 -3
1 1 5
5
6 1 3
0 3 -2 5 -4 -4

样例输出 #1

1
2
3
4
5
6
7
6
0
1
0
0
1
9

提示

在示例的第一组测试数据中，Dima 可以选择任何一天进行旅行，因此适合他的日期有 [1]、[2]、[3]、[1, 2]、[2, 3] 和 [1, 2, 3]。

在示例中的第二组和第四组测试数据中，由于气温过高，Dima 无法在任何一天出行，因此没有适合的日期。

在示例的第三组测试数据中，Dima 只能在日期 [1, 2, 3] 进行旅行。

题解

题目解析

一道求区间长度的题,题目需要我们求当区间长度大于等于 $k$ 时,连续天数的个数.通过B站dalao的讲解,提供了一种 $O(n)$ 方法,就是相当于一个 $f(x)$ 函数在 $y=q$ 画一条线,只要底下的部分.

我的做法是利用题目中给的 $q$ 来把连续区间存到一个数组里,然后用等差数列求和公式来求得在这个区间的所有情况.详细内容放到代码注释里.

AC代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define endl "\n"
#define MAXN(size) const long long MAXN = size + 100
#define var(size) int p[size]{}
#define mem(name,value) memset(name,value,sizeof(name))
#define fa(a,n,p) for(int i=a;i<=n;i+=p)
#define fb(a,n,p) for(int i=a;i>=n;i-=p)
#define cin(length,var) for(int i=1;i<=length;i++) cin >> var[i]
typedef long long ll;

MAXN(2e5);
int p[MAXN];
ll a[MAXN][3];

signed main(){
	int T;
	cin >> T;
	while(T--){
		int n,k,q,cunt=0;
		ll ans = 0;
		cin >> n >> k >> q;
		cin(n,p);
		fa(1,n,1)
			if(p[i] > q)//把温度大于q的区间标出来
				p[i] = -0x3f3f3f3f;
		fa(1,n,1){
			if(p[i] > -0x3f3f3f3f){//如果第一个点温度小于q
				int l=i,r=i;
				a[++cunt][1] = l;//标一下左起点
				while(p[i] > -0x3f3f3f3f && i <= n)
					r++,i++;
				a[cunt][2] = r;//标一下右终点
			}
		}
		fa(1,cunt,1)
			if(a[i][2] - a[i][1] >= k)//如果长度大于等于k
				ans += (a[i][2] - a[i][1] - k + 1)*(a[i][2] - a[i][1] - k + 2) / 2;
		cout << ans << endl;
	}
	return 0;
}