【BZOJ-1178】CONVENTION会议中心 倍增 + set (神思路好题!)

时间:2022-09-11 21:47:26

1178: [Apio2009]CONVENTION会议中心

Time Limit: 15 Sec  Memory Limit: 162 MB
Submit: 812  Solved: 323
[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

Sample Output

2
1 3

HINT

修复数据bug,并新加数据一组By NanoApe 2016.5.11

修复后数据:JudgeOnline/upload/201605/dd.rar

Source

Solution

思路非常神

首先我们如果只要求数目最多,显然可以贪心,即线段覆盖

字典序最小就很麻烦了

方法还是贪心,按照读入的顺序,判断,如果使当前满足,能够达到最优,那么就选当前

问题是如何加速判断的过程

$f[i][j]$表示,以$i$时间开始,选$2^{j}$条线段后,右端点最近在哪

这个信息显然是可以合并的,那么倍增解决

判断的时候,用数据结构维护一下就可以,比如用set查询前驱后继

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<set>
using namespace std;
int read()
{
int x=,f=; char ch=getchar();
while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}
while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}
return x*f;
}
#define MAXN 200010
#define INF 0x3f3f3f3f
int N;
struct CompanyNode{int s,t,id;}c[MAXN],tmp[MAXN],b[MAXN];
bool cmp1(CompanyNode A,CompanyNode B) {return A.s==B.s? A.t>B.t : A.s<B.s;}
bool cmp2(CompanyNode A,CompanyNode B) {return A.id<B.id;}
struct SetNode
{
int x,f;
SetNode (int x,int f) : x(x),f(f) {}
bool operator < (const SetNode & A) const
{return x<A.x;}
};
set<SetNode>st;
set<SetNode>::iterator lst,rst;
int f[MAXN<<][];
int Cal(int l,int r)
{
int re=;
for (int i=; i>=; i--)
if (f[l][i]<=r) l=f[l][i]+,re+=<<i; //一定要+1
return re;
}
int ls[MAXN<<],tp,top;
int main()
{
//freopen("data.in","r",stdin); freopen("data.out","w",stdout);
N=read();
for (int i=; i<=N; i++) ls[++tp]=c[i].s=read(),ls[++tp]=c[i].t=read(),c[i].id=i;
sort(ls+,ls+tp+);
top=unique(ls+,ls+tp+)-ls-;
for (int i=; i<=N; i++)
c[i].s=lower_bound(ls+,ls+top+,c[i].s)-ls,c[i].t=lower_bound(ls+,ls+top+,c[i].t)-ls;
sort(c+,c+N+,cmp1);
int last=INF; tp=;
for (int i=N; i>=; i--) if (c[i].t<last) tmp[++tp]=c[i],last=c[i].t;
reverse(tmp+,tmp+tp+);
// for (int i=1; i<=tp; i++) printf("%d %d %d\n",tmp[i].s,tmp[i].t,tmp[i].id);
memset(f,0x3f,sizeof(f));
// printf("%d %d\n",f[1],INF);
for (int i=top,j=tp; i>=; i--)
{
f[i][]=f[i+][];
if (tmp[j].s==i) f[i][]=min(f[i][],tmp[j].t);
for (int k=; k<=; k++)
if (f[i][k-]!=INF)
f[i][k]=f[f[i][k-]+][k-];
while (tmp[j].s==i) j--;
}
// for (int i=1; i<=N; i++) printf("%d %d %d\n",c[i].id,c[i].s,c[i].t);
printf("%d\n",Cal(,top));
sort(c+,c+N+,cmp2);
st.insert(SetNode(,-)); st.insert(SetNode(top+,));
int cnt=;
for (int i=; i<=N; i++)
{
SetNode ls=SetNode(c[i].s,),rs=SetNode(c[i].t,-);
lst=st.lower_bound(ls); rst=st.upper_bound(rs);
if (lst!=rst || (*rst).f==-) continue;
lst--;
int L=(*lst).x+,R=(*rst).x-;
if (Cal(L,c[i].s-)+Cal(c[i].t+,R)+==Cal(L,R))
{
st.insert(ls),st.insert(rs);
cnt++; if (cnt==) printf("%d",c[i].id); else printf(" %d",c[i].id);
}
}
puts("");
return ;
}