cdoj 04 Complete Building the Houses 暴力
Complete Building the Houses
Time Limit: 20 Sec Memory Limit: 256 MB
题目连接
http://acm.uestc.edu.cn/#/problem/show/3
Description
Bear has a large, empty ground for him to build a home. He decides to build a row of houses, one after another, say n in total.
The houses are designed with different height. Bear has m workers in total, and the workers must work side by side. So at a time bear can choose some continuous houses, no more than m, and add their heights by one, this takes one day to finish.
Given the designed height for each house, what is the minimum number of days after which all the houses’ heights are no less than the original design?
Input
The first line of input contains a number T, indicating the number of test cases. (T≤50)
For each case, the first line contains two integers n and m: the number of houses and the number of workers. The next line comes with n non-negative numbers, they are the heights of the houses from left to right. (1≤n,m≤100,000, each number will be less than 1,000,000,000)
Output
For each case, output Case #i: first. (i is the number of the test case, from 1 to T). Then output the days when bear’s home can be built.
Sample Input
2
3 3
1 2 3
3 3
3 2 1
Sample Output
Case #1: 3
Case #2: 3
HINT
题意
你想修n栋房子,高度分别为a[i],你一次最多可以同时修m栋连在一起的房子,然后问你最少多久能修完这些房子
题解:
暴力做就好了,直接从最左边考虑然后搞搞搞就好了
代码:
//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define test freopen("test.txt","r",stdin)
#define maxn 200000
#define mod 10007
#define eps 1e-9
int Num;
char CH[];
const int inf=0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fLL;
inline ll read()
{
ll x=,f=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
}
inline void P(int x)
{
Num=;if(!x){putchar('');puts("");return;}
while(x>)CH[++Num]=x%,x/=;
while(Num)putchar(CH[Num--]+);
puts("");
}
//************************************************************************************** ll dp[maxn];
void solve()
{
ll n,m,a,sum=,ans=;
n=read(),m=read();
for(int i=;i<n;i++)
{
a=read();
if(i>=m)sum-=dp[i-m];
dp[i]=;
if(a>sum)
{
ans+=a-sum;
dp[i]=a-sum;
sum=a;
}
}
cout<<ans<<endl;
}
int main()
{
//test;
int t=read();
for(int cas=;cas<=t;cas++)
{
printf("Case #%d: ",cas);
solve();
}
}
最新文章
- Intent属性详解一 component属性
- github仓库的克隆、修改、上传方法(图)
- AsyncTask实现断点续传
- 转: CentOS 6.4安装pip,CentOS安装python包管理安装工具pip的方法
- ACM题目————数素数
- 从基础开始,从一个SQLHelper开始
- 创建本地Ubuntu镜像
- 获取Ip 的地域等信息接口-实例
- 使用 NuGet 管理项目库
- -force_load
- 使用EasyUI的树控件构建Web界面
- python子域名收集器
- MATLAB中“repmat”与“cat”函数的用法
- mysql入门练习
- 史上最简单的SpringCloud教程 | 第七篇: 高可用的分布式配置中心(Spring Cloud Config)
- C#中子线程操作主线程中窗体上控件的方法
- iOS开发ffmpeg SDK 编译和集成
- 维护keepalived与mysql漂移脚本
- storm报错:Exception in thread ";main"; java.lang.RuntimeException: InvalidTopologyException(msg:Component: [mybolt] subscribes from non-existent stream: [default] of component [kafka_spout])
- Python码农福音,GitHub增加Python语言安全漏洞告警