会议中心

会议中心

时间: 1ms        内存:128M

描述:

Siruseri政府建造了一座新的会议中心。许多公司对租借会议中心的会堂很感兴趣,他们希望能够在里面举行会议。 对于一个客户而言,仅当在开会时能够独自占用整个会堂,他才会租借会堂。会议中心的销售主管认为:最好的策略应该是将会堂租借给尽可能多的客户。显然,有可能存在不止一种满足要求的策略。 例如下面的例子。总共有4个公司。他们对租借会堂发出了请求,并提出了他们所需占用会堂的起止日期(如下表所示)。

上例中,最多将会堂租借给两家公司。租借策略分别是租给公司1和公司3,或是公司2和公司3,也可以是公司1和公司4。注意会议中心一天最多租借给一个公司,所以公司1和公司2不能同时租借会议中心,因为他们在第九天重合了。
销售主管为了公平起见,决定按照如下的程序来确定选择何种租借策略:首先,将租借给客户数量最多的策略作为候选,将所有的公司按照他们发出请求的顺序编号。对于候选策略,将策略中的每家公司的编号按升序排列。最后,选出其中字典序最小1的候选策略作为最终的策略。 例中,会堂最终将被租借给公司1和公司3:3个候选策略是{(1,3),(2,3),(1,4)}。而在字典序中(1,3)<(1,4)<(2,3)。 你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

对于50%的输入,N≤3000。在所有输入中,N≤200000。

-------------------

1 字典序指在字典中排列的顺序,如果序列l1是序列l2的前缀,或者对于l1和l2的第一个不同位置j,l1[j]<l2[j],则l1比l2小。

输入:

输入的第一行有一个整数N,表示发出租借会堂申请的公司的个数。第2到第N+1行每行有2个整数。第i+1行的整数表示第i家公司申请租借的起始和终止日期。对于每个公司的申请,起始日期为不小于1的整数,终止日期为不大于109的整数。

输出:

输出的第一行应有一个整数M,表示最多可以租借给多少家公司。第二行应列出M个数,表示最终将会堂租借给哪些公司。

示例输入:

4
4 9
9 11
13 19
10 17

示例输出:

2
1 3

提示:

参考答案(内存最优[41628]):

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <set>
#define M 200005
#define inf 0x3f3f3f3f
using namespace std;
int f[M*2][19],l[M*2],L[M*2],N,cnt,m,n;
struct data
{
    int s,e,id;
}a[M],b[M],c[M];
struct rec
{
    int x,k;
}le,ri;
set<rec> s;
set<rec>::iterator itl,itr;
bool cmp1(data a,data b)
{
    if (a.s==b.s) return a.e>b.e;
    return a.s<b.s;
}
bool cmp2(data a,data b)
{
    return a.id<b.id;
}
bool operator <(rec a,rec b)
{
    return a.x<b.x;
}
void Prepare()
{
    sort(l+1,l+1+m);
    for (int i=1;i<=m;i++)
        if (i==1||l[i]!=l[i-1])
            L[++N]=l[i];
    for (int i=1;i<=n;i++)
    {
        a[i].s=lower_bound(L+1,L+1+N,a[i].s)-L;
        a[i].e=lower_bound(L+1,L+1+N,a[i].e)-L;
    }
    sort(a+1,a+1+n,cmp1);
    for (int i=n;i;i--)
        if (a[i].e<inf) b[++cnt]=a[i];
    for (int i=1;i<=cnt;i++)
        c[i]=b[cnt-i+1];
    memcpy(b,c,sizeof(c));
    memset(f,0x3f,sizeof(f));
    for (int i=N,j=cnt;i;i--)
    {
        f[i][0]=f[i+1][0];
        if (b[j].s==i) f[i][0]=min(f[i][0],b[j].e);
        for (int k=1;k<=17;k++)
            if (f[i][k-1]!=inf)
                f[i][k]=f[f[i][k-1]+1][k-1];
        while (b[j].s==i)
            j--;
    }
}
int Calc(int l,int r)
{
    int ans=0;
    for (int i=17;i>=0;i--)
        if (f[l][i]<=r)
            l=f[l][i],ans+=1<<i;
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].s,&a[i].e);
        a[i].id=i;
        l[++m]=a[i].s,l[++m]=a[i].e;
    }
    Prepare();
    cout<<Calc(1,N)<<endl;
    sort(a+1,a+1+n,cmp2);
    le.x=0,le.k=2,ri.x=N+1,ri.k=1;
    s.insert(le),s.insert(ri);
    for (int i=1;i<=n;i++)
    {
        le.x=a[i].s,le.k=1,ri.x=a[i].e,ri.k=2;
        itl=s.lower_bound(le);
        itr=s.upper_bound(ri);
        if (itl!=itr||itr->k==2) continue;
        itl--;
        int ll=itl->x+1,rr=itr->x-1;
        if (Calc(ll,a[i].s-1)+Calc(a[i].e+1,rr)+1!=Calc(ll,rr))
            continue;
        s.insert(le),s.insert(ri);
        printf(i!=n-1?"%d ":"%d\n",a[i].id);
    }
    return 0;
}

参考答案(时间最优[24]):

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
#include <set>
#define M 200005
#define inf 0x3f3f3f3f
using namespace std;
int f[M*2][19],l[M*2],L[M*2],N,cnt,m,n;
struct data
{
    int s,e,id;
}a[M],b[M],c[M];
struct rec
{
    int x,k;
}le,ri;
set<rec> s;
set<rec>::iterator itl,itr;
bool cmp1(data a,data b)
{
    if (a.s==b.s) return a.e>b.e;
    return a.s<b.s;
}
bool cmp2(data a,data b)
{
    return a.id<b.id;
}
bool operator <(rec a,rec b)
{
    return a.x<b.x;
}
void Prepare()
{
    sort(l+1,l+1+m);
    for (int i=1;i<=m;i++)
        if (i==1||l[i]!=l[i-1])
            L[++N]=l[i];
    for (int i=1;i<=n;i++)
    {
        a[i].s=lower_bound(L+1,L+1+N,a[i].s)-L;
        a[i].e=lower_bound(L+1,L+1+N,a[i].e)-L;
    }
    sort(a+1,a+1+n,cmp1);
    for (int i=n;i;i--)
        if (a[i].e<inf) b[++cnt]=a[i];
    for (int i=1;i<=cnt;i++)
        c[i]=b[cnt-i+1];
    memcpy(b,c,sizeof(c));
    memset(f,0x3f,sizeof(f));
    for (int i=N,j=cnt;i;i--)
    {
        f[i][0]=f[i+1][0];
        if (b[j].s==i) f[i][0]=min(f[i][0],b[j].e);
        for (int k=1;k<=17;k++)
            if (f[i][k-1]!=inf)
                f[i][k]=f[f[i][k-1]+1][k-1];
        while (b[j].s==i)
            j--;
    }
}
int Calc(int l,int r)
{
    int ans=0;
    for (int i=17;i>=0;i--)
        if (f[l][i]<=r)
            l=f[l][i],ans+=1<<i;
    return ans;
}
int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d",&a[i].s,&a[i].e);
        a[i].id=i;
        l[++m]=a[i].s,l[++m]=a[i].e;
    }
    Prepare();
    cout<<Calc(1,N)<<endl;
    sort(a+1,a+1+n,cmp2);
    le.x=0,le.k=2,ri.x=N+1,ri.k=1;
    s.insert(le),s.insert(ri);
    for (int i=1;i<=n;i++)
    {
        le.x=a[i].s,le.k=1,ri.x=a[i].e,ri.k=2;
        itl=s.lower_bound(le);
        itr=s.upper_bound(ri);
        if (itl!=itr||itr->k==2) continue;
        itl--;
        int ll=itl->x+1,rr=itr->x-1;
        if (Calc(ll,a[i].s-1)+Calc(a[i].e+1,rr)+1!=Calc(ll,rr))
            continue;
        s.insert(le),s.insert(ri);
        printf(i!=n-1?"%d ":"%d\n",a[i].id);
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注