首页 > 代码库 > BZOJ3433: [Usaco2014 Jan]Recording the Moolympics

BZOJ3433: [Usaco2014 Jan]Recording the Moolympics

2024-07-25 15:27:39   225人阅读

3433: [Usaco2014 Jan]Recording the Moolympics

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 55  Solved: 34
[Submit][Status]

Description

 Being a fan of all cold-weather sports (especially those involving cows), Farmer John wants to record as much of the upcoming winter Moolympics as possible. The television schedule for the Moolympics consists of N different programs (1 <= N <= 150), each with a designated starting time and ending time. FJ has a dual-tuner recorder that can record two programs simultaneously. Please help him determine the maximum number of programs he can record in total.

给出n个区间[a,b).有2个记录器.每个记录器中存放的区间不能重叠.

求2个记录器中最多可放多少个区间.

 

 

Input

* Line 1: The integer N.

* Lines 2..1+N: Each line contains the start and end time of a single program (integers in the range 0..1,000,000,000).

Output

* Line 1: The maximum number of programs FJ can record.

Sample Input

6
0 3
6 7
3 10
1 5
2 8
1 9

INPUT DETAILS: The Moolympics broadcast consists of 6 programs. The first runs from time 0 to time 3, and so on.

Sample Output

4

OUTPUT DETAILS: FJ can record at most 4 programs. For example, he can record programs 1 and 3 back-to-back on the first tuner, and programs 2 and 4 on the second tuner.

HINT

 

Source

Silver 鸣谢Alegria_提供译文

题解：
随便打了个贪心居然就过了23333，是数据弱还是怎么？
将区间按右端点排序，维护now[0],now[1]分别表示两个记录器最后的位置
新来的线段先往now大的那个记录器放，放不下再到小的那个里，否则会出现大材小用。。。（提示：过不了样例。。。）
不知道对不对？？？挖坑，以后来想。
代码：
 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 100014 #define maxm 500+10015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}28     while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}29     return x*f;30 }31 int now[2],n,ans;32 struct rec{int x,y;}a[maxn];33 inline bool cmp(rec a,rec b)34 {35     return a.y<b.y;36 }37 int main()38 {39     freopen("input.txt","r",stdin);40     freopen("output.txt","w",stdout);41     n=read();42     for1(i,n)a[i].x=read(),a[i].y=read();43     sort(a+1,a+n+1,cmp);44     now[0]=now[1]=0;45     for1(i,n)46      {47          if(a[i].x>=now[1])ans++,now[1]=a[i].y;48          else if(a[i].x>=now[0])ans++,now[0]=a[i].y;49          if(now[0]>now[1])swap(now[0],now[1]);50      }51     printf("%d\n",ans);52     return 0;53 }
View Code

 

BZOJ3433: [Usaco2014 Jan]Recording the Moolympics


联系
我们