HDU—— 5159 Building Blocks
LeLe has already built piles.
He wants to move some blocks to make consecutive
piles with exactly the same height .
LeLe already put all of his blocks in these piles, which means he can
not add any blocks into them. Besides, he can move a block from one pile
to another or a new one,but not the position betweens two piles already
exists.For instance,after one move,"3 2 3"
can become "2 2 4" or "3 2 2 1",but not "3 1 1 3".
You are request to calculate the minimum blocks should LeLe move.
The first line of input contains three integers . indicate piles
blocks.
For the next line ,there are integers indicate
the height of each piles.
The height of a block is 1.
If there is no solution, output "-1" (without quotes).
问题描述 看完电影后,乐乐回家玩起了积木。
他已经搭好了堆积木,他想通过调整积木,使得其中有连续堆积木具有相同的高度,同时他希望高度恰好为
乐乐的积木都这了,也就是说不能添加新的积木,只能移动现有的积木。
他可以把一个积木从一堆移动到另一堆或者新的一堆,但是不能移动到两堆之间。比如,一次移动之后,"3 2 3" 可以变成 "2 2 4" 或者 "3 2 2 1",但是不能变成"3 1 1 3".
请你帮他算算,需要移动的最少积木数。 输入描述 有多组测试数据,大约组。
第一行三个整数,
表示有多少堆积木。
第二行个元素,表示这座积木的高度。
所有数据的范围 ; 输出描述 输出最少需要移动的次数,如果无法完成输出-。 输入样例 输出样例 - Hint 样例解释:把第3座积木上的一个积木移动到第1座上,前3座积木的高度就变成了2 ,就得到了一个3*(积木必须是连续的W堆)。
解题思路:首先记录n个数值的总和,然后每次以w长度对数组进行遍历,切每次对w区间长度内的数值进行处理,将每个大于H的A[i]与H的差值累加赋给t1,将每个小于H的A[i]与H的差值累加赋给t2,然后将t1,t2中较大的值与上次的ans比较取出最小值赋给ans,ans表示该w长度内满足条件时所需移动的次数,然后往下移动即t1或t2中移除一个a[i-w],然后添加一个a[i],最后输出ans即可。
分析:
首先看对于一个连续的W堆,若要将其高度全变为h,我们可以计算出各个堆与h的差值,用s1累加低于h的部分,s2累加超出h的部分。则最少需要移动的次数为max(s1,s2),这是因为:使低于h的部分达到h需要s1个积木,这s1个可以从s2中补得,也可以从其他积木中获得;而使得超出h的积木达到h,需要移走s2个,这s2个可以移动到低于h的积木上,也可以移动到其他积木或者新堆中。于是取s1,s2的较大值,这样一定可以使得这连续的W堆高度均为h。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define INT_MAX 1e9+10
typedef long long LL;
int n, w, h;
int a[]; int main()
{
freopen("ini.txt","r",stdin);
while (~scanf("%d%d%d", &n, &w, &h))
{
fill(a, a + , );
LL sum = , t1 = , t2 = ;//t1代表高度超过H的总和,t2高度小于H的总和,sum表示所有输入a[i]值的总和
int i = ;
for (; i < w; i++) //数组a[i]的前端增加w个0
{
a[i] = a[i] - h; //a[i]-h表示每个a[i]值与h的差值,并将该差值赋给a[i]
t2 += -a[i]; //将差值小于0的累加赋给t2保存
}
for (; i < n + w; i++)
{
scanf("%d", &a[i]);
sum += a[i];
a[i] = a[i] - h; //将每个a[i]替换成a[i]-h的差值
}
for (; i < n + * w; i++)
a[i] = a[i] - h; LL ans = INT_MAX;
ans = max(t1, t2); //将t1、t2中的最大值赋给ans,ans表示每次移动的次数,
if (sum < w*h)
printf("-1\n"); //sum小于w*h直接输出-1
else //否则遍历后边的区间
{
for (int j = w; j<n + * w; j++)
{
if (a[j - w] > )
t1 -= a[j - w];//t1移除前面一个a[i]值
else
t2 += a[j - w];//t2移除后面一个a[i]值 if (a[j] > )
t1 += a[j];//t1往后添加一个a[i]值
else
t2 += -a[j];//t2往后添加一个a[i]值 ans = min(ans, max(t1, t2));//每次找出最小值赋给ans
}
printf("%I64d\n", ans);
}
}
return ;
}
最新文章
- ASP.NET执行模型之IIS服务器处理流程
- springmvc图片上传
- Redis的安装、配置 --转载
- android 窗体透明的,黑暗度等的设置技巧
- 使用Code::Blocks配置Python编译环境
- redis入门指南-第7章-管理
- JavaSE教程-04Java中循环语句for,while,do&#183;&#183;&#183;while
- PHP将数据导出Excel表中(投机型)
- Windows Server 2016-Windows安全日志ID汇总
- story 泄露服务器libc版本
- loading js备份
- PHP生成PDF并转换成图片爬过的坑
- mongoDB工具类以及测试类【java】
- openstack详细笔记-nova-glance-swift-cinder-keystone等
- 未在本地计算机上注册“Microsoft.ACE.OLEDB.12.0
- 用 Django 做了一个照片分享网站
- Xshell6和Xftp下载地址,rzsz的使用
- 170503、centos6.5安装mysql5.6.30
- can&#39;t start Git: git.exe
- zigbee路由(报文实例)