首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >【POJ1083】 Moving Tables (并行的搬运)

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

作者头像
饶文津
发布2020-06-02 14:19:22
3180
发布2020-06-02 14:19:22
举报
文章被收录于专栏:饶文津的专栏饶文津的专栏

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;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017-03-19 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • 题解
  • 代码
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档