首页 > 试题广场 >

CodeForces 363B Fence

[编程题]CodeForces 363B Fence

热度指数：6 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

There is a fence in front of Polycarpus's home. The fence consists of n planks of the same width which go one after another from left to right. The height of the i -th plank is h _i meters, distinct planks can have distinct heights.

<center> $\text{[math]}$ Fence for n = 7 and h = [1, 2, 6, 1, 1, 7, 1] </center>

Polycarpus has bought a posh piano and is thinking about how to get it into the house. In order to carry out his plan, he needs to take exactly k consecutive planks from the fence. Higher planks are harder to tear off the fence, so Polycarpus wants to find such k consecutive planks that the sum of their heights is minimal possible.

Write the program that finds the indexes of k consecutive planks with minimal total height. Pay attention, the fence is not around Polycarpus's home, it is in front of home (in other words, the fence isn't cyclic).

输入描述:

The first line of the input contains integers n and k (1 ≤ n ≤ 1.5·10⁵, 1 ≤ k ≤ n) — the number of planks in the fence and the width of the hole for the piano. The second line contains the sequence of integers h₁, h₂, ..., h_n (1 ≤ h_i ≤ 100), where h_i is the height of the i-th plank of the fence.

输出描述:

Print such integer j that the sum of the heights of planks j, j + 1, ..., j + k - 1 is the minimum possible. If there are multiple such j's, print any of them.

示例1

输入

7 3<br />1 2 6 1 1 7 1<br />

输出

3<br />

备注:

In the sample, your task is to find three consecutive planks with the minimum sum of heights. In the given case three planks with indexes 3, 4 and 5 have the required attribute, their total height is 8.

算法知识视频讲解

week_

这道题比较简单，没有什么弯弯绕。甚至可以一边接收一遍处理。

import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while (sc.hasNext()){
            int n=sc.nextInt();
            int k=sc.nextInt();
            int num[]=new int[n];
            for(int i=0;i<n;i++){
                num[i]=sc.nextInt();
            }

            int sum=0;
            int index=0;
            for(int i=0;i<k;i++){
                sum=sum+num[i];
            }
            int min=sum;
            for(int i=k;i<n;i++){
                sum=sum-num[i-k]+num[i];
                if(sum<min){
                    min=sum;
                    index=i-k+1;
                }
            }
            System.out.println(index+1);
        }
    }
}

发表于 2019-06-06 19:46:38 回复(0)