专栏首页饶文津的专栏【POJ1083】 Moving Tables (并行的搬运)

【POJ1083】 Moving Tables (并行的搬运)

BUPT2017 wintertraining(15) #6E

题意

房间1和2,3和4,...,399和400共用一节走廊,有q次从房间li到ri的搬运桌子,一次搬运10分钟。两个搬运如果走廊有重叠部分,则必须一个结束后再执行另一个。求全部搬运所需最少的时间。

题解

对于一次搬运,我们可以求出它经过的走廊区间,给这些区间的每节走廊的经过次数都++。最少的总时间就是最大经过次数*10。 这题贪心为什么不对呢?贪心的方法是根据区间右端点排序,右端点相同再按左端点排序。然后如果当前的左端点小于前一个的右端点则ans+=10。但是这种情况不一定需要ans+10,因为更前面的搬运也许不和当前区间重叠,因此可以和它并行。例如[1,2],[2,3],[3,4],贪心的话答案是30,但[1,2],[3,4]可以同时进行,所以正确答案是20。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
int t,n,ans,v[300];
int main() {
	scanf("%d",&t);
	while(t--){
		memset(v,0,sizeof v);
		ans=0;
		scanf("%d",&n);
		for(int i=1,l,r;i<=n;i++){
			scanf("%d%d",&l,&r);
			if(l>r)swap(l,r);
			l=(l+1)/2;
			r=(r+1)/2;
			for(int j=l;j<=r;j++)v[j]++;
		}
		for(int i=1;i<=200;i++)ans=max(ans,v[i]);
		printf("%d\n",ans*10);
	}
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【 Gym - 101124E 】Dance Party (数学)

    BUPT2017 wintertraining(15) #4G Gym - 101124 E.Dance Party

    饶文津
  • 【CodeForces 699A】Launch of Collider

    饶文津
  • 【USACO 3.2】Factorials(阶层非零尾数)

    题解:可以把5和2的个数算出来,每次把5和2都除掉,最后乘上比5多出来的2。我的解法是,每次把尾巴的0去掉,并且保留3位,算到最后取尾数就可以了。、

    饶文津
  • 【蓝桥杯】BASIC-12 十六进制转八进制

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • LeetCode 273. Integer to English Words

    ShenduCC
  • 2019年广东工业大学腾讯杯新生程序设计竞赛(同步赛)E-缺席的神官

    链接:https://ac.nowcoder.com/acm/contest/3036/E 来源:牛客网 题目描述 面前的巨汉,让我想起了多年前的那次,但...

    风骨散人Chiam
  • 小程序实践(四):动态控制组件的显示/隐藏

    组件有个属性:hidden='' ,值为true/false ,当false的时候说明不隐藏,当true的时候说明隐藏,注意该隐藏是不保留组件位置的。

    听着music睡
  • leetcode394. Decode String

    将一个字符串解码,要求按照次数展开原字符串中的中括号。如3[a]2[bc]对应的字符串就是aaabcbc,即a展开3次,bc展开2次。注意,源字符串中的括号是允...

    眯眯眼的猫头鹰
  • 空降兵如何管理团队?

    张树臣
  • 优秀的markdown书写工具--Typora

    Typora ? typora ? typora 下载地址 https://www.typora.io/

    听城

扫码关注云+社区

领取腾讯云代金券