题目链接:uva 1444 - Knowledge for the masses
题目大意:给出R和L,R表示有R行,L表示一行的最大长度。
对于每一行,给出n,然后是n个数,arr[i]为0表示空格,长度为1,否则表示书架,长度为arr[i]。现在人要从上边走到下边,问说最少移动几个书架,并且输出可以通过的路径坐标。
解题思路:c[i]表示第i个坐标有多少行可以通过,当c[i]==R时,表示人可以从该位置穿过整个书架。g[i]表示从i这个位置穿过的代价。然后对于每一行处理,pos[i]记录第i个空格的位置,vis[i]记录左移的代价,用来和右移代价作比较,取最小值。注意第二行输出的时候每个数后面都要根空格,否则PE。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6+5;
const int INF = 0x3f3f3f3f;
int R, L, c[maxn], g[maxn];
int n, arr[maxn], pos[maxn], vis[maxn];
void input () {
scanf("%d", &n);
memset(vis, -1, sizeof(vis));
int cnt = 0, mv = 0;
for (int i = 0; i < n; i++) {
scanf("%d", &arr[i]);
if (arr[i] == 0) {
mv++;
pos[cnt++] = i;
c[mv-1]++;
} else {
int k = min(cnt, arr[i]);
mv = mv + arr[i];
for (int j = 1; j <= k; j++) {
int u = mv - j;
vis[u] = i - pos[cnt-j] - j + 1;
g[u] += vis[u];
c[u]++;
}
}
}
reverse(arr, arr+n);
cnt = 0;
for (int i = 0; i < n; i++) {
if (arr[i] == 0) {
mv--;
pos[cnt++] = i;
} else {
int k = min(cnt, arr[i]);
mv = mv - arr[i];
for (int j = 0; j < k; j++) {
int u = mv + j;
if (vis[u] == -1) {
vis[u] = i - pos[cnt-j-1] - j;
g[u] += vis[u];
c[u]++;
} else {
int tmp = i - pos[cnt-j-1] - j;
g[u] += min(0, tmp - vis[u]);
}
}
}
}
}
void init () {
scanf("%d%d", &R, &L);
memset(c, 0, sizeof(c));
memset(g, 0, sizeof(g));
for (int i = 0; i < R; i++)
input();
}
void solve () {
int ans = INF, cnt = 0;
for (int i = 0; i < L; i++) {
if (c[i] == R) {
if (g[i] < ans) {
cnt = 0;
ans = g[i];
}
if (g[i] == ans)
vis[cnt++] = i;
}
}
printf("%d\n", ans);
for (int i = 0; i < cnt; i++)
printf("%d ", vis[i]);
printf("\n");
}
int main () {
int cas;
scanf("%d", &cas);
while (cas--) {
init();
solve();
}
return 0;
}
分享到:
相关推荐
Dr Bobbs-CUDA Supercomputing for the Masses共21篇经典博客文章整理版,该系列文章为NVIDIA官方网站培训中心推荐的博文,非常值得学习GPU和CUDA编程的人看
类似于CUDA深入浅出的教程,来自于Nvidia官网的链接网站,我可是花了2个多小时才把源格式内容拷到DOC文档里的,呵呵。。欢迎下载,共同学习CUDA!
【由浅入深的教程,源代码讲解较多】适合入门兼进阶的人学习,连贯性强!!!
Secrets of Podcasting: Audio Blogging for the Masses <br>播客秘密 <br>作者: Bart G. Farkas 出版商: Peachpit Press (August 9, 2005) 内容介绍: 如果你认为互联网广播很酷,那么你将经历...
计算相似度的matlab代码A-trace-map-comparison-algorithm-for-the-discrete-fracture-network-models-of-rock-masses 一种岩体离散裂缝网络模型的迹图比对算法论文题目:一种岩体离散裂缝网络模型的迹图比对算法...
Google Cardboard is one of the most accessible ways to experience virtual reality today. This book introduces developers to this exciting new platform ...Chapter 5 Google Cardboard - VR for the Masses
OCaml的介绍,OCaml是一种为表达,安全和速度而设计的工业级编程语言。 里面的示例将帮助读者快速了解OCaml作为编写快速,简洁和易读的系统代码的工具如何脱颖而出。
信息安全_数据安全_Auditd_for_the_Masses 安全架构解决方案 渗透测试 安全测试 安全现状
The revolt of the masses – the growing power of suppliers......Page 164 More for less – the problem of growing complexity......Page 174 The growing strains – overloading the beasts of burden.........
GEMpire是一款免费的,多人游戏,客户端/服务器,用Java编写的Empire游戏,其基本概念与Empire Deluxe类似。 它被写成允许改变帝国规则以探索有趣的变化。 由于其客户端/服务器架构
A Software-Defined Radio for the Masses, Part 1
Massmine-For-The-Masses是一种开源的概念验证工具。它扩展了Massmine的功能,Massmine是一个命令行界面,它是一种数据收集工具。 Massmine-For-The-Masses具有图形用户界面,使用户可以查看从不同平台(如Twitter...
['Auditd for the Masses.pdf', 'Building Systems On Shaky Grounds 10 Tactics To Manage The Modern Supply Chain.pdf', 'Drones the new weapon of choice - also for hackers.pdf', 'From printed circuit ...
I want to thank you and congratulate you for downloading the book, “Python Programming For Beginners: Learn The Basics Of Python In 7 Days!” This book will help you to understand the basics of ...
The World Wide Web has been credited with bringing the Internet to the masses. The Internet was previously the stomping ground of academics and a small, elite group of computer professionals, mostly...
Chapter 1 The Bold New World of Web Analytics 2.0 1 Chapter 2 The Optimal Strategy for Choosing Your Web Analytics Soul ...Chapter 14 HiPPOs, Ninjas, and the Masses: Creating a Data-Driven Culture 407
资源分类:Python库 所属语言:Python 资源全名:water-masses-2021.1.0a3.tar.gz 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
has never been an option for the masses before. Now with the XNA Framework, games can be written for the console. By the end of the book, readers will have created two complete games and many demos ...
This paper presents a novel and easy implementing method computing masses from the hundreds of pieces of data collected by a WSN. The transfer model is based on the Mahalanobis distance (MD), which ...
* The masses are connected by springs whose length, damping constant and spring constant can be freely chosen by the algorithm. * The loads must never touch the ground. The optimality of a ...