CodeForces 363B Fence
Fence
This problem will be judged on CodeForces. Original ID: 363B
64-bit integer IO format: %I64d Java class name: (Any)
Fence for n = 7 and h = [1, 2, 6, 1, 1, 7, 1]
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).
Input
The first line of the input contains integers n and k (1 ≤ n ≤ 1.5·105, 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 h1, h2, ..., hn (1 ≤ hi ≤ 100), where hi is the height of the i-th plank of the fence.
Output
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.
Sample Input
7 3
1 2 6 1 1 7 1
3
Hint
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.
Source
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
int n,k,sum[maxn];
int main(){
while(~scanf("%d %d",&n,&k)){
int theMin = INT_MAX,idx = -;
for(int i = ; i <= n; ++i){
scanf("%d",sum+i);
sum[i] += sum[i-];
if(i >= k && sum[i] - sum[i-k] < theMin){
theMin = sum[i] - sum[i-k];
idx = i - k + ;
}
}
printf("%d\n",idx);
}
return ;
}
最新文章
- 牛逼的css3:动态过渡与图形变换
- jstl中格式化时间戳
- 【RabbitMQ】RabbitMQ的一些基础概念
- mysql grant ,User,revoke
- SSIS ->;>; 生成时间格式
- 通过AopTestUtils对切面对象进行mock
- 安装TDM-GCC
- Jsp连接Mysql数据库取数方法
- 职责链(Chain of Responsibility)模式
- HDU 1681 Frobenius(完全背包+标记装满)
- 浅谈一个网页打开的全过程(涉及DNS、CDN、Nginx负载均衡等)
- YII2 models非常好用的控制输出数据【重写Fields】
- Core Animation 文档翻译 (第五篇)
- [CentOS] rsync同步目录进行备份文件
- 获取多个checkbox的选中值
- 移动电源、3G路由拆机
- [译]CQRS介绍
- Python2.7-hashlib
- jQuery页面滚动图片等元素动态加载实现
- PAT 乙级 1037 在霍格沃茨找零钱(20)C++版