「BZOJ3433」[Usaco2014 Jan] Recording the Moolympics
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.
题解
按右端点排序贪心
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<set> #define inf 1000000000 #define ll long long using namespace std; inline int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,l1,l2,ans; struct data{int x,y;}a[155]; inline bool operator<(data a,data b) { return a.y<b.y; } int main() { n=read(); for(int i=1;i<=n;i++) a[i].x=read(),a[i].y=read(); sort(a+1,a+n+1); for(int i=1;i<=n;i++) { if(a[i].x>=l1)l1=a[i].y,ans++; else if(a[i].x>=l2)l2=a[i].y,ans++; if(l1<l2)swap(l1,l2); } printf("%d",ans); return 0; } |
OI 课件=>
