HDU 5191 Building Blocks
2024-08-25 19:36:31
题目链接:
hdu:http://acm.hdu.edu.cn/showproblem.php?pid=5191
bc(中文):http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=572&pid=1002
题解:
要在原始的n堆前面扩展w个空堆,同时在原始n堆后面扩展w个空堆,然后对[0,w+n+w)这个区间考虑所有的长度为w的子区间,计算出需要移动的方块数,更新答案。
代码:
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
typedef long long LL; const int maxn = +; int n;
LL w, h;
int arr[maxn*]; void init() {
memset(arr, , sizeof(arr));
} int main() {
while (scanf("%d%lld%lld", &n, &w,&h) == && n) {
init();
LL sum = ;
for (int i = ; i < n; i++) {
scanf("%d", arr + i+w);
sum += arr[i+w];
}
if (sum < w*h) {
printf("-1\n");
continue;
}
//cntf:总共需要填入多少个方块,cntz:总共需要移出多少个方块,cnt保存连续w个的初始和
LL cntz = ,cntf=w*h, cnt = ;
LL ans = w*h;
for (int i = w; i < *w+n; i++) {
//计算新窗口的cntz,cntf,cnt;
if (arr[i - w] - h>) cntz -= (arr[i - w] - h);
else cntf -= (h - arr[i - w]);
cnt -= arr[i - w];
if (arr[i] - h > ) cntz += arr[i] - h;
else cntf += h - arr[i];
cnt += arr[i]; LL tmp;
if (w*h > cnt) tmp =cntf;
else tmp = cntz; ans = min(ans, tmp);
} printf("%lld\n", ans);
}
return ;
}
最新文章
- 5种io模式
- mysql 根据某字段特定值排序
- 图解集合5:不正确地使用HashMap引发死循环及元素丢失
- 利用scp 远程上传下载文件/文件夹和ssh远程执行命令
- EasyUI中Dialog的使用
- android ExpandableListView详解
- PHP 防范IP攻击
- 【2014】【辛星】【php】【秋季】【2】第一个php程序
- Python之路,Day10 - 异步IO\数据库\队列\缓存
- 使用Android SDK Manager自动下载速度慢解决方法
- 在IIS上Office Word下载失败,检索 COM 类工厂中 CLSID 为000209FF的组件失败,80070005 拒绝访问。
- hdu 3228 (最大流+二分)
- mysql基础之对库表操作
- 分布式:2PC,3PC,Paxos,Raft,ISR [转]
- c语言基础学习02_windows系统下的cmd命令
- numpy使用总结
- vue v-if 和 v-show 的知识点
- MySQL 中 having 和 where 的区别
- [Swift]LeetCode720. 词典中最长的单词 | Longest Word in Dictionary
- php操作redis数据库方法总结
热门文章
- 《Redis设计与实现》- 数据库
- redis应用场景:实现简单计数器-防止刷单
- 今天差点被断电搞死了,幸好IDE的备份救了我
- 字符编码——python学习
- 内置函数--eval
- PTA基础编程题目集6-6求单链表结点的阶乘和(函数题)
- 微信小程序 request请求封装
- 【win7下安装node.js错误:roling back action】与【";grunt"; 不是内部或外部命令】 解决方法
- 20155310 《Java程序设计》实验三(敏捷开发与XP实践)实验报告
- 20155310第一周JAVA实验报告