bzoj1178 [Apio2009]CONVENTION会议中心 区间dp+贪心
2024-10-19 02:18:57
[Apio2009]CONVENTION会议中心
Time Limit: 15 Sec Memory Limit: 162 MB
Submit: 1130 Solved: 444
[Submit][Status][Discuss]
Description
Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣,他们希望能够在里面举行会议
。 对于一个客户而言,仅当在开会时能够独自占用整个会堂,他才会租借会堂。会议中心的销售主管认为:最好
的策略应该是将会堂租借给尽可能多的客户。显然,有可能存在不止一种满足要求的策略。 例如下面的例子。总
共有4个公司。他们对租借会堂发出了请求,并提出了他们所需占用会堂的起止日期(如下表所示)。 开始日期
结束日期 公司1 4 9 公司2 9 11 公司3 13 19 公司4 10 17 上例中,最多将会堂租借给两家公司。租借策略分别
是租给公司1和公司3,或是公司2和公司3,也可以是公司1和公司4。注意会议中心一天最多租借给一个公司,所以
公司1和公司2不能同时租借会议中心,因为他们在第九天重合了。 销售主管为了公平起见,决定按照如下的程序
来确定选择何种租借策略:首先,将租借给客户数量最多的策略作为候选,将所有的公司按照他们发出请求的顺序
编号。对于候选策略,将策略中的每家公司的编号按升序排列。最后,选出其中字典序最小1的候选策略作为最终
的策略。 例中,会堂最终将被租借给公司1和公司3:3个候选策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(
1,4)<(2,3)。 你的任务是帮助销售主管确定应该将会堂租借给哪些公司。
Input
第一行有一个整数N,表示发出租借会堂申请的公司的个数。
第2到第N+1行每行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。
对于每个公司的申请,起始日期为不小于1的整数,终止日期为不大于10^9的整数。
N≤200000
Output
输出的第一行应有一个整数M,表示最多可以租借给多少家公司。
第二行应列出M个数,表示最终将会堂租借给哪些公司。
Sample Input
4
4 9
9 11
13 19
10 17
4 9
9 11
13 19
10 17
Sample Output
2
1 3
1 3
HINT
修复数据bug,并新加数据一组By NanoApe 2016.5.11
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<set> #define inf 1000000007
#define N 200007
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m;
int X[N],Y[N],next[N][],L[N],R[N];
struct data
{
int l,r;
friend bool operator < (const data &x,const data &y)
{
return x.r==y.r ? x.l>y.l : x.r<y.r;
}
}a[N],t[N]; int cal(int l,int r) {
int x=lower_bound(X+,X++m,l)-X;
if (Y[x]>r || x>m) return ;
int res=;
for (int i=;i>=;i--) if (next[x][i] && Y[next[x][i]]<=r) res+=<<i,x=next[x][i];
return res;
}
int main()
{
n=read();
for (int i=;i<=n;i++)
t[i].l=read(),t[i].r=read(),a[i]=t[i];
sort(t+,t++n); m=;
for (int i=;i<=n;i++)
if (m==||t[i].l>t[m].l) t[++m]=t[i];
for (int i=;i<=m;i++)
X[i]=t[i].l,Y[i]=t[i].r;
for (int i=,j=;i<=m;i++)
{
while (j<=m&&t[j].l<=t[i].r) j++;
if (j<=m) next[i][]=j;
}
for (int j=;j<=;j++)
for (int i=;i<=m;i++)
next[i][j]=next[next[i][j-]][j-];
int ans;
printf("%d\n",ans=cal(-inf,inf));
set<data> s;
s.insert((data){inf,inf});
s.insert((data){-inf,-inf});
int cnt=;
for (int i=;i<=n;i++)
{
set<data>::iterator x=s.lower_bound(a[i]),y=x;y--;
int l1=y->r,r1=a[i].l,l2=a[i].r,r2=x->l;
if (l1>=r1||l2>=r2) continue;
if (cal(l1+,r2-)==cal(l1+,r1-)+cal(l2+,r2-)+)
{
if (++cnt==ans) printf("%d",i);
else printf("%d ",i);
s.insert(a[i]);
}
}
}
最新文章
- OpenLayers简单介绍以及简单实例
- javaSE第十二天
- NSNumber、NSValue、NSDate、NSObject
- 安装sybase12.0,运行时报错异常。
- lintcode:在二叉查找树中插入节点
- PLSQL Developer Debug
- fragment中获取activity中的控件
- IIS网站发布容易出现的几个问题
- Java集合概述、Set集合(HashSet类、LinkedHashSet类、TreeSet类、EnumSet类)
- 2018-2019-1 20189210 《LInux内核原理与分析》第七周作业
- 【linux】ftp使用端口转发问题
- Sprint会议计划
- The zero inflated negative binomial distribution
- 7.3 C++模板中的函数式参数
- Alpha冲刺 - (10/10)
- 二维数组与类的定义_DAY06
- Alpha版使用说明
- Socket心跳包机制总结【转】
- Matlab练习——素数查找
- 简单计算器的C实现-函数指针,main函数传参