ACM一道题,这题用线段树都没办法,数据太大了LL's cafeTime Limit:5 Sec Memory Limi

问题描述：

ACM一道题,
这题用线段树都没办法,数据太大了
LL's cafe
Time Limit:5 Sec Memory Limit:128 MBSubmissions:127 Solved:47
Description
LL opens a new cafe and he knows N customers will come tomorrow and the time of their appearance and departure.LL wants to know how many seats he should buy in advance to hold all customers tomorrow at least.Note :1.One seat can only hold one customer at any time.2.Suppose A leave at time t,and B come at time t,then they can’t sit at the same seat.
Input
There are multiple cases ended with EOF.Every case is terminated with a blank line .The first number of each case is one number——N (1

1个回答分类：英语 2014-11-14

问题解答：

我来补答

/>#include<iostream>
#include<algorithm>
using namespace std;
struct TV{
\x05int begin;
\x05int end;
}Tv[100005];
bool cmp(TV a,TV b)
{
\x05return a.end < b.end;
}
int main()
{
\x05int n,i;
\x05while(scanf("%d",&n)!=EOF)
\x05{
\x05\x05int cnt=0;
\x05\x05for(i=0;i<n;i++)
\x05\x05\x05scanf("%d%d",&Tv[i].begin,&Tv[i].end);
\x05\x05sort(Tv,Tv+n,cmp);
\x05
\x05\x05int End=Tv[0].end;
\x05\x05for(i=1;i<n;i++){
\x05\x05\x05if(Tv[i].begin>End)
\x05\x05\x05{
\x05\x05\x05\x05cnt++;
\x05\x05\x05\x05End=Tv[i].end;
\x05\x05\x05}
\x05\x05}
\x05\x05printf("%d\n",n-cnt);
\x05}
\x05return 0;
}
参考这个代码哈.

思路：
首先把开始时间都从早到晚排序,然后从第一个开始往下数,（同时设一个comp标志,用来进行比较）.情况有主要两种.

1. 只要Ti[i].e即结束时间比上comp.e还早,那么,我们就选中这个而抛弃原来的comp.e,并把这个Ti[i].s还有Ti[i].e标志为comp.
2. 只要Ti[i].s大于comp.s,我们就要在num上加一,即在加一个可以坐的位置.同时将次节目的Ti[i].s以及Ti[i].e标志为comp.s和comp.e .
再问：这个题要是0

展开全文阅读