寒光博客

[CF]#576A. City Day
Codeforces Round #576 (Div. 2) 问题链接(https://codeforces.co...
扫描右侧二维码阅读全文
04
2019/08

[CF]#576A. City Day

Codeforces Round #576 (Div. 2)
问题链接(https://codeforces.com/problemset/problem/1199/A)

问题描述

A.City Day

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;
            }
        }
    }
}
本文作者:Author:     文章标题:[CF]#576A. City Day
本文地址:https://dxoca.cn/Algorithm/216.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:August 8th, 2019 at 08:01 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment