[好题] 关键字：求k小数。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
PP大厦有一间空的礼堂，可以为企业或者单位提供会议场地。这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不 同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与 这个申请相冲突的预约。 一般来说，如果PP大厦方面事先已经接受了一个会场预约，例如从10日到15日，就不会在接受与之相冲突的预约，例如从12日到17日。不过，有时出于经 济利益，PP大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。 于是，礼堂管理员QQ的笔记本上笔记本上经常记录着这样的信息： 本题中为方便起见，所有的日期都用一个整数表示。例如，如果一个为期10天的会议从“90日”开始到“99日”，那么下一个会议最早只能在“100日”开 始。 最近，这个业务的工作量与日俱增，礼堂的管理员QQ希望参加SHTSC的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作： A操作：有一个新的预约是从“start日”到“end日”，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒 绝掉的预约个数，以方便QQ与自己的记录相校对。 B操作：请你的系统返回当前的仍然有效的预约的总数。
Input Format
第一行是一个整数n，表示你的系统将接受的操作总数。 接下去n行每行表示一个操作。每一行的格式为下面两者之一： “A start end”表示一个A操作； “B”表示一个B操作。
Output Format
有n行，每行一次对应一个输入。表示你的系统对于该操作的返回值。
Sample Input #1
6
A 10 15
A 17 19
A 12 17
A 90 99
A 11 12
B
Sample Output #1
0
0
2
0
1
2
Hint
N< = 200000
1< = Start End < = 100000
当读入一个新的预约时，不断查找已经存在的预约中end值大等于新预约start值，并且最接近该start值的预约，找到一个删除一个，直到不能删除为 止。因为不冲突的预约都是不相互覆盖的，所以它们的start值与end值必然是递增序列，所以一旦一个预约不能删除，后面的预约也不能删除。
这样，问题就转换成了：寻找最小的比给定的数x大的数。该问题解法非常多，这里写得非常不错：http://www.cnblogs.com/wuyiqi/archive/2011/12/25/2301071.html
当然，这个问题除了用树状数组以及平衡树，线段树也是可以做的。思想仍然是二分。本题可以做为k大数的模版题。
#include <stdio.h>
int n,ans = 0,cnt;
int list[200010][2],sum[140010],id[140010];
int lowbit(int x)
{
return x&(-x);
}
void add(int pos,int x)
{
for(;pos<=140000;pos+=lowbit(pos)) sum[pos] += x;
}
int query(int pos)
{
int tans = 0;
for(;pos;pos-=lowbit(pos)) tans += sum[pos];
return tans;
}
int findKth(int x)
{
int i,t,tsum = 0,tans = 0;
for(i=16,t=1<<16;i>=0;i--,t>>=1)
{
tans += t;
if(tsum+sum[tans]>=x) tans -= t;
else tsum += sum[tans];
}
return tans+1;
}
int main()
{
int i = 0,t,p;
char opt;
scanf("%d\n",&n);
while(n--)
{
scanf("%c",&opt);
if(opt == 'A')
{
i++; cnt = 0;
scanf(" %d %d\n",&list[i][0],&list[i][1]); id[list[i][1]] = i;
t = query(list[i][0]-1);
for(p = findKth(t+1);list[id[p]][0]>0&&list[id[p]][0]<=list[i][1];cnt++,ans--,add(p,-1),p = findKth(t+1));
ans++; add(list[i][1],1);
printf("%d\n",cnt);
}
else
{
scanf("\n");
printf("%d\n",ans);
}
}
return 0;
}
评论 (0)
