ACM一道题,这题用线段树都没办法,数据太大了LL's cafeTime Limit:5 Sec Memory Limi
来源:学生作业帮 编辑:神马作文网作业帮 分类:英语作业 时间:2024/09/27 08:17:50
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
这题用线段树都没办法,数据太大了
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
/>#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
#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
ACM一道题,这题用线段树都没办法,数据太大了LL's cafeTime Limit:5 Sec Memory Limi
一道acm题,Delete NumberTime Limit:1000MS Memory Limit:65536KTot
一道acm题,Problem H:Groups (I)Time Limit:1000MS Memory Limit:65
求编程此题思路球Case Time Limit:1000MSTime Limit: 3000MS Memory Limi
ACM题一道,原题 zstuoj2511Delete NumberTime Limit:1000MS Memory Li
一道数学的ACM题.1514:x + 2y + 3z = nTime Limit:1000MS Memory Limit
新手请教ACM水题Q - 数据的交换输出Time Limit:1000MS Memory Limit:32768KB 6
SequenceTime Limit:1 Sec Memory Limit:128 MBSubmissions:254
ACM水题,WA了,请问错在哪里了?对称文 Time Limit:1000MS Memory Limit:32768KD
ACM 的一道题提交总是Time Limit Exceeded,求救
英语翻译是浙大ACM题库的题目 看不懂Crazy SearchTime Limit:5 Seconds Memory L
ACM的 “顺”序列 Time Limit:1000MS Memory Limit:32768K