【bzoj 3433】{Usaco2014 Jan} Recording the Moolympics（算法效率--贪心）

题意：给出n个区间[a,b)，有2个记录器，每个记录器中存放的区间不能重叠。求2个记录器中最多可放多少个区间。

解法：贪心。只有1个记录器的做法详见——关于贪心算法的经典问题（算法效率 or 动态规划）。而对于2个，就是在1个的基础上（按 bi 排序，选第一个与之前没有相交的区间）维护2个值，注意要好好for循环遍历一次O(n)，若想着用while直接跳过一些区间很容易出错！！！另外，遍历时要先考虑能否把当前的区间接在之前右端点较右的记录器。

 1 #include<cstdio>

 2 #include<cstdlib>

 3 #include<cstring>

 4 #include<iostream>

 5 #include<algorithm>

 6 using namespace std;

 7

 8 const int N=155;

 9 struct node{int l,r;}a[N];

10

11 int read()

12 {

13     char ch=getchar();

14     int x=0;

15     while (ch<'0'||ch>'9') ch=getchar();

16     while (ch>='0'&&ch<='9') x=x*10+ch-'0', ch=getchar();

17     return x;

18 }

19 bool cmp(node x,node y) {return x.r<y.r;}

20 int main()

21 {

22     int n=read();

23     for (int i=1;i<=n;i++)

24     {

25       a[i].l=read(),a[i].r=read();

26       if (a[i].l>a[i].r) {int t;t=a[i].l,a[i].l=a[i].r,a[i].r=t;}

27     }

28     sort(a+1,a+1+n,cmp);

29     int cnt=0,x=0,y=0;

30     for (int i=1;i<=n;i++)

31     {

32       if (x<=a[i].l) cnt++,x=a[i].r;

33       else if (y<=a[i].l) cnt++,y=a[i].r;

34       if (x<y) {int tmp;tmp=x,x=y,y=tmp;}

35     }

36     printf("%d\n",cnt);

37     return 0;

38 }

巴特西

【bzoj 3433】{Usaco2014 Jan} Recording the Moolympics（算法效率--贪心）

最新文章

热门文章