「BZOJ3410」[Usaco2009 Dec] Selfish Grazing 自私的食草者
Description
约翰有N(1≤N≤50000)头牛，约翰的草地可以认为是一条直线．每只牛只喜欢在某个特定的范围内吃草．第i头牛喜欢在区间(Si，Ei)吃草，1≤Si<Ei≤1,000,000,00.
奶牛们都很自私，他们不喜欢和其他奶牛共享自己喜欢吃草的领域，因此约翰要保证任意
两头牛都不会共享他们喜欢吃草昀领域．如果奶牛i和奶牛J想要同时吃草，那么要满足：Si>=Ej或者Ei≤Sj．约翰想知道在同一时刻，最多可以有多少头奶牛同时吃草？
Input
第1行：一个整数N．
第2到N+1行：第i+l行有两个整数Si，Ei．
Output
一个整数，最多可以有多少头牛同时吃草．
Sample Input
5
2 4
1 12
4 5
7 10
7 8
2 4
1 12
4 5
7 10
7 8
Sample Output
3
HINT
第1，3，4共3只奶牛可以同时吃草，第1，3，5也可以．
题解
逗我。。。
|
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 39 40 41 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<set> #include<map> #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,ans; struct data{int a,b;}a[50005]; bool operator<(data a,data b) { return a.b<b.b; } int main() { n=read(); for(int i=1;i<=n;i++) a[i].a=read(),a[i].b=read(); sort(a+1,a+n+1); int now=0; for(int i=1;i<=n;i++) if(now<=a[i].a) { now=a[i].b; ans++; } printf("%d",ans); return 0; } |
Subscribe
计数器 9860171
OI 课件=>
OI 课件=>