Codeforces Round #576 (Div. 2)
问题链接(https://codeforces.com/problemset/problem/1199/A)
问题描述
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.
Input
The first line contains three integers n, x and y (1≤n≤100000, 0≤x,y≤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 a1, a2, ..., an ($1 \le a_i \le 10^9$), where ai denotes the rain amount on the i-th day.
Output
Print a single integer — the index of the earliest not-so-rainy day of summer. We can show that the answer always exists.
给n,x,y，以及这n天的下雨量ai。要找一天(下标为)d，要求这一天的下雨量是这一天前x天到后y天的下雨量中最小的。输出最早的(下标最小的)d。保证答案一定存在。
问题分析
第一次 做cf的题，读懂题目有点艰难qwq 细节上的问题嘛，，翻译不好 然后找了方哥帮忙搞了一下
读懂题目全部都变得很简单了，思路也基本和大佬的一致，但是再实现和细节处理上就蛮多问题
如下代码是学习之后的。 max min 分段 用的妙啊~！！🤗
因为x,y的最大可能值为7，很小，所以直接遍历去找即可。注意处理好边界问题。
代码
package cf;
import java.util.Scanner;
import static java.lang.Integer.min;
import static java.lang.Math.max;
public class cityday {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int x = cin.nextInt();
int y = cin.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = cin.nextInt();
}
for (int i = 0; i < n; i++) {
boolean flag=true;
for (int j = (max(i-x,0)); j < i; j++) {
if(a[j]<a[i]){
flag=false;
break;
}
}
if(!flag)continue;
for (int j = min(i+y,n-1); j >i ; j--) {
if(a[j]<a[i]){
flag=false;
break;
}
}
if(flag){
System.out.println(i+1);
return;
}
}
}
}本文地址：https://dxoca.cn/Algorithm/216.html 百度已收录
版权说明：若无注明，本文皆为“Dxoca's blog （寒光博客）”原创，转载请保留文章出处。
