306449: CF1199A. City Day
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
City Day
题意翻译
### 题目描述 很多年了,N市的节日是在下雨天最严重的那一天举行。新的领导者打算去打破这个传统,并准备选择一个下雨天不是那么严重的一天进行活动。领导者知道$n$天的天气预报。在第$i$天上,下$a_i$毫米的雨。 领导者知道市民们关注$x$天前以及$y$天后的天气。因此,他说假定第$d$天下雨不是那么严重在满足以下情况 1. 满足$a_d<a_j$ 2. $j$满足$d-x \leq j<d$或者$d<j \leq d+y$ 由于市民们只看n天,所以j同时还要满足$1 \leq j \leq n$ 请帮助领导者找到下雨不是那么严重的一天 ### 输入格式 第一行输入$n$,$x$,$y$,他们满足$1 \leq n \leq 100000$, $0 \leq x,y \leq 7$ 第二行输入$a_1$,$a_2$,...,$a_n$,他们满足$1 \leq a_i \leq 10^9$ ### 输出格式 输出最早的下雨不是那么严重的一天 ### 说明/提示 #### 第一个样例 第3天和第8天都满足这个条件,第三天更早,所以答案是第三个。 #### 第二个样例 第三天不满足这个条件,因为$3+y=6$ 且 $a_3>a_6$。第8天是答案。请注意:$8+y=11$,然而我们没有第11天,所以无需考虑第11天。题目描述
For years, the Day of city N was held in the most rainy day of summer. New mayor decided to break this tradition and select a not-so-rainy day for the celebration. The mayor knows the weather forecast for the $ n $ days of summer. On the $ i $ -th day, $ a_i $ millimeters of rain will fall. All values $ a_i $ are distinct. The mayor knows that citizens will watch the weather $ x $ days before the celebration and $ y $ days after. Because of that, he says that a day $ d $ is not-so-rainy if $ a_d $ is smaller than rain amounts at each of $ x $ days before day $ d $ and and each of $ y $ days after day $ d $ . In other words, $ a_d < a_j $ should hold for all $ d - x \le j < d $ and $ d < j \le d + y $ . Citizens only watch the weather during summer, so we only consider such $ j $ that $ 1 \le j \le n $ . Help mayor find the earliest not-so-rainy day of summer.输入输出格式
输入格式
The first line contains three integers $ n $ , $ x $ and $ y $ ( $ 1 \le n \le 100\,000 $ , $ 0 \le x, y \le 7 $ ) — the number of days in summer, the number of days citizens watch the weather before the celebration and the number of days they do that after. The second line contains $ n $ distinct integers $ a_1 $ , $ a_2 $ , ..., $ a_n $ ( $ 1 \le a_i \le 10^9 $ ), where $ a_i $ denotes the rain amount on the $ i $ -th day.
输出格式
Print a single integer — the index of the earliest not-so-rainy day of summer. We can show that the answer always exists.
输入输出样例
输入样例 #1
10 2 2
10 9 6 7 8 3 2 1 4 5
输出样例 #1
3
输入样例 #2
10 2 3
10 9 6 7 8 3 2 1 4 5
输出样例 #2
8
输入样例 #3
5 5 5
100000 10000 1000 100 10
输出样例 #3
5