201901-B - Moving Tables

2024-02-07 05:30
文章标签 moving tables 201901

本文主要是介绍201901-B - Moving Tables,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

@201901冬训

B - Moving Tables

题目:

The famous ACM (Advanced Computer Maker) Company has rented a floor of a building whose shape is in the following figure.

在这里插入图片描述
The floor has 200 rooms each on the north side and south side along the corridor. Recently the Company made a plan to reform its system. The reform includes moving a lot of tables between rooms. Because the corridor is narrow and all the tables are big, only one table can pass through the corridor. Some plan is needed to make the moving efficient. The manager figured out the following plan: Moving a table from a room to another room can be done within 10 minutes. When moving a table from room i to room j, the part of the corridor between the front of room i and the front of room j is used. So, during each 10 minutes, several moving between two rooms not sharing the same part of the corridor will be done simultaneously. To make it clear the manager illustrated the possible cases and impossible cases of simultaneous moving.
在这里插入图片描述
For each room, at most one table will be either moved in or moved out. Now, the manager seeks out a method to minimize the time to move all the tables. Your job is to write a program to solve the manager’s problem.

input

The input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each test case begins with a line containing an integer N , 1 <= N <= 200, that represents the number of tables to move.

Each of the following N lines contains two positive integers s and t, representing that a table is to move from room number s to room number t each room number appears at most once in the N lines). From the 3 + N -rd

line, the remaining test cases are listed in the same manner as above.

output

The output should contain the minimum time in minutes to complete the moving, one per line.

sample input

3
4
10 20
30 40
50 60
70 80
2
1 3
2 200
3
10 100
20 80
30 50

sample output

10
20
30

题目大意是在这个走廊两侧分别有200个房间,会给出一些数字对a,b表示要从a搬一张桌子到b,搬一次花费10分钟,搬的过程中a到b间(包括a,b处)的过道都是被占用的,不能再搬其他桌子。要求找到花费的最少时间。
题目给的是两侧,但其实奇数偶数都是一样的—从2到4搬桌子时,1到3的过道也是被占用的,所以读入时可以处理一下a,b,让a=(a+1)/2,b=(b+1)/2。
我一开始想到的办法是贪心,将数对排序,首先右侧升序,其次左侧降序,这样利用空间最大,然后不断遍历直到都搬完。
但最好的方法是:用一个数组记录第i间房间被占用的次数,然后求占用次数最大值即可。

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
struct no{int a,b,c;
}s[202];
int n,ans=0;
int str(no aa,no bb)
{   if(aa.c!=bb.c)return aa.c<bb.c;if(aa.b!=bb.b)return aa.b<bb.b;return aa.a>bb.a;
}
int main()
{int t;cin>>t;while(t--){ans=0;cin>>n;for(int i=0;i<n;i++){cin>>s[i].a>>s[i].b;s[i].a=(s[i].a +1)/2; s[i].b=(s[i].b +1)/2;s[i].c=0;}int nn=n;sort(s,s+n,str);  for(int i=0;i<n;i++)while(nn){   int lasa=0,lasb=0,de=0;for(int i=0;i<n;i++)if(s[i].c==0)if(s[i].a>lasb){s[i].c=1;lasa=s[i].a;lasb=s[i].b;de++;} nn=nn-de;ans++;} cout<<ans*10<<endl;}return 0;
}

这篇关于201901-B - Moving Tables的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/686636

相关文章

HumanNeRF:Free-viewpoint Rendering of Moving People from Monocular Video 翻译

HumanNeRF:单目视频中运动人物的自由视点绘制 引言。我们介绍了一种自由视点渲染方法- HumanNeRF -它适用于一个给定的单眼视频ofa人类执行复杂的身体运动,例如,从YouTube的视频。我们的方法可以在任何帧暂停视频,并从任意新的摄像机视点或甚至针对该特定帧和身体姿势的完整360度摄像机路径渲染主体。这项任务特别具有挑战性,因为它需要合成身体的照片级真实感细节,如从输入视频中可能

【0323】Postgres内核之 hash table sequentially search(seq_scan_tables、num_seq_scans)

0. seq scan tracking 我们在这里跟踪活跃的 hash_seq_search() 扫描。 需要这种机制是因为如果扫描正在进行时发生桶分裂(bucket split),它可能会访问两次相同的条目,甚至完全错过某些条目(如果它正在访问同一个分裂的桶中的条目)。因此,如果正在向表中插入数据,我们希望抑制桶分裂。 在当前的使用中,这种情况非常罕见,因此只需将分裂推迟到下一次插入即可。

DBA_TABLES ALL_TABLES USER_TABLES

DBA_TABLES ALL_TABLES USER_TABLES DBA_TABLES >= ALL_TABLES >= USER_TABLES DBA_TABLES意为DBA拥有的或可以访问的所有的关系表。 ALL_TABLES意为某一用户拥有的或可以访问的所有的关系表。 USER_TABLES意为某一用户所拥有的所有的关系表。 由上可知,当某一用户本身就为数据库DBA时,DBA_

【并查集】 HDU 1213 How Many Tables

HDU 1213 How Many Tables 纯粹的并查集 #include <iostream>#include <string>#include <algorithm>#include <math.h>#include <stdio.h>#include <stdlib.h>using namespace std;int father[1111];int get_fa(

Fatal error: Can't open and lock privilege tables: Table 'mysql.user' doesn't exist解决办法

问题 用安装版的Mysql确实没有二进制版的简单,自己配置,随心所欲。今天在安装二进制版的Mysql 5.7的时候出现了如下错误。 看了一下配置文件,配置的没有问题。然后再启动的时候确实出现了没创建mysql库的情况。我也不知道为啥,上网查吧……网上也没告诉我为啥。只是告诉我解决办法,根据解决办法可以很明显的看出是初始化出了问题,但是原理是什么我也不清楚…… 解决办法 1、先将my.

346. Moving Average from Data Stream

https://leetcode.com/problems/moving-average-from-data-stream/description/ 题目大意:初始化一个滑动窗口,大小为w,输入一系列数,求窗口内的平均数,窗口会向前滑动,当窗口填满时,将最早进入的数弹出,加入新的数. 解题思路:用队列,求和时可以利用上次的和,不用每次从头到尾求 代码: class MovingAverag

PostgreSQL的系统视图pg_statio_all_tables

PostgreSQL的系统视图pg_statio_all_tables pg_statio_all_tables 是 PostgreSQL 中的一个系统视图,提供数据库中所有表的 I/O 数据。这些信息可以帮助你理解表的读取和写入操作,从而优化数据库性能。 下面是 pg_statio_all_tables 系统视图的字段解释: relid: 表的 OID(对象标识符)。schemaname:

PostgreSQL的视图pg_tables

PostgreSQL的视图pg_tables pg_tables 是 PostgreSQL 中的一个系统视图,用于显示当前数据库中所有用户定义的表的信息。这个视图提供了关于表的名称、所属模式(schema)、所有者以及表类型等详细信息。 pg_tables 视图的主要列 列名类型描述schemanamename表所在的模式(schema)名称。tablenamename表的名称。tableo

PostgreSQL的视图pg_stat_user_tables

PostgreSQL的视图pg_stat_user_tables pg_stat_user_tables 是 PostgreSQL 中的一个系统视图,用于显示用户定义的表的统计信息。这些统计信息包括表的访问情况、修改情况以及很多其他的性能指标。这个视图为数据库管理员提供了丰富的数据,可以帮助他们进行表的监控和性能分析。 pg_stat_user_tables 视图的主要列和其含义 列名类型描

UVA - 10201 Adventures in Moving - Part IV

题意:在100升为初始的车,求到达终点的最小花费,路上有加油站,分别给你离起点的距离和每升油的价格,没升油走一公里,在选与不选做动态规划 #include <iostream>#include <cstdio>#include <cstring>#include <algorithm>#include <cmath>using namespace std;const int MAXN