hdu 1050 Moving Tables(迷之贪心...)
2024-08-31 02:04:27
题意:有400间房间按题目中图片所给的方式排列,然后给出要移动的n张桌子所要移动的范围,每张桌子要移动的范围不能出现重叠的区域;问最少要多少次才能移动完所有的桌子。
题解思路:把题目转换下,就是有n个区间,每次可以去除掉k个没有重叠部分的区间,最少要多少次能去掉所有区间。妥妥的,,贪心。可能会有人联想到经典的“区间调度问题”。但很遗憾,在这里行不通;区间调度问题是按区间右端排序后尽可能选取结束时间早的,但这种贪心只是一次性选取尽可能多的区间,而本题是要求选取完所有区间所要花费次数最少。从整体上看,如果只是每次找到尽可能多的区间,对一次的遍历从房间尾号排序确实达到了这样的目的,但整体目的却不是这样的,因为最终是要把所有的区间都找完的,并不是说仅仅找最多的一次,你还要顾及后面的让每一次都尽可能找得更多的房间。所以不管前几次怎样,你现在要找的这一次需要越靠前开始找。 因此正解应该是按区间左端排序,然后每次找最靠前的。 虽然看完上面的解释可能还是会不怎么明白为什么第一种贪心是错的,那就测试下面这组数据琢磨琢磨吧:
Input Output
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <map>
#include <queue>
#include <stack>
const int inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double EPS=1e-;
using namespace std;
typedef long long ll;
typedef pair<int,int> P; int T,n;
typedef struct node
{
int l,r;
} node;
node a[];
bool cmp(node a,node b)
{
return a.l<b.l;
}
int book[];
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
int l,r;
for(int i=; i<=n; i++)
{
scanf("%d%d",&l,&r);
a[i].l=(l%)?(l/+):l/;
a[i].r=(r%)?(r/+):r/;
if(a[i].l>a[i].r) swap(a[i].l,a[i].r);
}
//
sort(a+,a++n,cmp);
//
memset(book,,sizeof(book));
int ans=;
int N=n;
while(n)
{
//printf("%d\n",n);
ans++;
int temp=;
while(book[temp]) temp++;
book[temp]=;
n--;
for(int i=temp+; i<=N; i++)
{
if(!book[i]&&a[i].l>a[temp].r)
{
n--;
book[i]=;
temp=i;
}
}
}
//
printf("%d\n",ans*);
}
return ;
}
还有另一种贪心方法更直接明了:计算出所有区间中最大的重叠次数,即答案。因为假设有块地方被k个区间所重叠,那么无论如何选择,这块地方肯定都是至少要k次才能移动完重叠在这上面的区间;而其他地方肯定也都能在k次以内移动完的。 计算重叠部分的话,,这题数据略水可以暴力过去...=_=
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <set>
#include <utility>
#include <vector>
#include <map>
#include <queue>
#include <stack>
const int inf=0x3f3f3f3f;
const double PI=acos(-1.0);
const double EPS=1e-;
using namespace std;
typedef long long ll;
typedef pair<int,int> P; int T,n;
typedef struct node
{
int l,r;
} node;
node a[];
int book[];
int main()
{
//freopen("input.txt","r",stdin);
scanf("%d",&T);
while(T--)
{
memset(book,,sizeof(book));
scanf("%d",&n);
int l,r;
for(int i=; i<=n; i++)
{
scanf("%d%d",&l,&r);
a[i].l=(l%)?(l/+):l/;
a[i].r=(r%)?(r/+):r/;
//
if(a[i].l>a[i].r) swap(a[i].l,a[i].r);
//
for(int j=a[i].l;j<=a[i].r;j++) book[j]++; }
int Max=-inf;
for(int i=;i<=;i++) Max=max(Max,book[i]);
printf("%d\n",Max*);
}
return ;
}
最新文章
- Async和Await异步编程的原理
- Java虚拟机12:Java内存模型
- MSCRM 2011/2013/2015 修改显示记录数
- mysql连接查询语句示例
- Leetcode 67 Add Binary 大数加法+字符串处理
- 十一、常用的NSArray和NSMutableArray方法
- 李洪强iOS开发之【Objective-C】09-空指针和野指针
- mysql和oracle日期和字符相互转换
- centos nginx 多端口配置过程记录
- MTRR内存类型范围寄存器
- PureMVC(JS版)源码解析(五):SimpleCommand类
- java正则表达式一:基本使用
- PHP - 直接输出对象的版本问题
- 最新Node.js 资源汇总
- bzoj2683简单题 cdq分治
- Javascript继承5:如虎添翼----寄生式继承
- [Web 前端] mobx教程(五)-Mobx常见问题及解决方案(1)Mobx使用严格模式
- centos命令行系列之centos6防火墙的关闭以及开启
- POJ 3067 - Japan - [归并排序/树状数组(BIT)求逆序对]
- 广通软件获“2016年度中国最具影响力IT运维管理软件提供商”殊荣
热门文章
- ACM_哥德巴赫猜想(素数筛)
- JSP所需要掌握的部分
- XML解析-Dom4j的DOM解析方式更新XML
- JQuery 记第N次被坑 - ajax请求字符集问题
- Java&;Xml教程(五)使用SAX方式解析XML文件
- android中textview单行显示,多余的省略
- JS高级——浏览器的线程
- JSP学习笔记 - 内置对象 Request
- Caffe2:ubuntu修改链接方式ln
- (转)Java任务调度框架Quartz入门教程指南(三)任务调度框架Quartz实例详解深入理解Scheduler,Job,Trigger,JobDetail