P3626 [APIO2009]会议中心

题目描述

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)。你的任务是帮助销售主管确定应该将会堂租借给哪些公司。

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

输入样例#1： 复制

4

4 9

9 11

13 19

10 17

输出样例#1： 复制

2

1 3

说明

对于 50%的输入，N≤3000。

在所有输入中，N≤200000。

题解

先让我吐槽一波。

今天教练给我们考倍增NOIP（Professional）模拟的考试题目。

第一题就是这一题，就第二题LCA模板？？？？

3，4都是NOI原题。肝了一下午。真棒。

接下来讲题解了。

考场上我想的是把一个线段的左端点排序。我不会告诉你我是从 \(1\) 跳到 \(n\)的

从 \(n\) 遍历到 \(1\) 然后二分最靠近它右端点的另一个线段的左端点。然后如果能跳到 \(i-1\) 的个数小于 \(i\)，那么就把 \(i-1\) 的信息都更新为 \(i\) 的，不然则把 \(i\) 的总值同等于 \(i-1\)。

这样的话我们就能在\(O(nlogn)\)的时间复杂度内搞出第一问了。

但是第二问怎么搞啊。

很明显的一个贪心：当我可以从多个线段跳过来的时候，我肯定是选择那个字典序最小的，那么，我就只需要在发现 \(i\) 的总值和 \(i-1\) 的总值相等时加一个暴力维护一下就好了，不相等就暴力更新。

时间复杂度是玄学的，可以被卡。但是X谷上还是跑的挺快的。

代码

#include<cstdio>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=200001;

const int fuck=99999999;

struct node{

    int l,r,id;

}ch[N];

int n,m,ans,cnt;

int sum[N],pre[N],now=99999999,line[N],minn[N],nn;

int read()

{

    int x=0,w=1;char ch=getchar();

    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}

    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();

    return x*w;

}

bool cmp(node a,node b){

    return a.l<b.l;

}

bool cmp2(node a,node b){

    return a.id<b.id;

}

int find (int x){

    int l=1,r=n,ans=0;

    while(r>l){

        int mid=(l+r)>>1;

        if(ch[mid].l>x)r=mid,ans=mid;

        else l=mid+1;

    }

    return r;

}

bool judge(int x,int y){

    int a=fuck,b=fuck;

    while(x!=y){

        a=min(ch[x].id,a);b=min(ch[y].id,b);

        x=pre[x];y=pre[y];

    }

    return a<b;

}

void solve()

{

    for(int i=n;i>=1;i--){

        int next=find(ch[i].r);

        sum[i]=1;minn[i]=i;pre[i]=fuck;

        if(ch[next].l>ch[i].r)sum[i]=sum[next]+1,pre[i]=minn[next];

        if(i!=n){

            if(sum[i+1]>sum[i])

            sum[i]=sum[i+1],minn[i]=minn[i+1],pre[i]=pre[i+1];

            if(sum[i+1]==sum[i]&&judge(minn[i+1],minn[i]))

            sum[i]=sum[i+1],minn[i]=minn[i+1],pre[i]=pre[i+1];

        }

    ans=max(ans,sum[i]);

}

    cout<<ans<<endl;

    int x=minn[1];

    while(x!=fuck){

        line[++cnt]=ch[x].id;

        x=pre[x];

    }

    sort(line+1,line+cnt+1);

    for(int i=1;i<=cnt;i++)

    cout<<line[i]<<' ';

}

int main()

{

//	freopen("interval.in","r",stdin);

//	freopen("interval.out","w",stdout);

    memset(minn,0x7f,sizeof(minn));

    n=read();

    for(int i=1;i<=n;i++)pre[i]=fuck;

    for(int i=1;i<=n;i++){

        ch[i].l=read();ch[i].r=read();ch[i].id=i;

    }

    sort(ch+1,ch+n+1,cmp);

    solve();

    return 0;

}

巴特西

[APIO2009]会议中心（贪心）

P3626 [APIO2009]会议中心

题目描述

输入输出格式

输入输出样例

说明

题解

代码

最新文章

热门文章