【uva 1617】Laptop（算法效率–贪心，2种理解）

题意：有N条长度为1的线段，要求使每条线段分别在相应区间，且“空隙”数目最小。输出“空隙”数。(1≤N≤100000)

解法：（P.S.我这题竟做了2个多小时，还是有点迷糊……ヽ(≧□≦)ノ）先按右端点从小到大排序，再是左端点。于是有2个理解：
1. 扫一遍，r保存之前的线段的右端点的最大值，分情况讨论；
2. （这个我理解了差不多1个小时……qwq 于是我好不容易理解了之后，再进行了一些小修改。）l , r 表示之前线段左、右端点的范围。再分别看没有“空隙”地加入当前线段的左、右端点的限制条件，若l+1>r，就说明这样不合法，便一定会有“空隔”。那便cnt++，并且最优化加入后当前的答案。

注意——许多贪心题都是排序后比较相邻两个的。比如我里面写的一些“区间相关问题”—— 关于贪心算法的经典问题（算法效率 or 动态规划）。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6
 7 const int N=100010;
 8 int n;
 9 struct node{int l,r;}a[N];
10
11 bool cmp(node x,node y)
12 {
13     if (x.r!=y.r) return x.r<y.r;
14     return x.l<y.l;
15 }
16 int main()
17 {
18     int T;
19     scanf("%d",&T);
20     while (T--)
21     {
22       scanf("%d",&n);
23       for (int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
24       sort(a+1,a+1+n,cmp);
25       int r=a[1].r,cnt=0;
26       for (int i=2;i<=n;i++)
27       //r为上一个线段能处于的最靠右的位置
28         if (r!=a[i].r)
29         {
30           if (r<a[i].l) cnt++,r=a[i].r;
31           else r++;
32         }
33       printf("%d\n",cnt);
34     }
35     return 0;
36 }

Code1

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6
 7 const int N=100010;
 8 int n;
 9 struct node{int l,r;}a[N];
10
11 int mmin(int x,int y) {return x<y?x:y;}
12 int mmax(int x,int y) {return x>y?x:y;}
13 bool cmp(node x,node y)
14 {
15     if (x.r!=y.r) return x.r<y.r;
16     return x.l<y.l;
17 }
18 int main()
19 {
20     int T;
21     scanf("%d",&T);
22     while (T--)
23     {
24       scanf("%d",&n);
25       for (int i=1;i<=n;i++) scanf("%d%d",&a[i].l,&a[i].r);
26       sort(a+1,a+1+n,cmp);
27       int l=a[1].l,r=a[1].r,cnt=0;
28       for (int i=2;i<=n;i++)
29       {
30         l=mmax(l+1,a[i].l),r=mmin(r+1,a[i].r);
31         if (l+1>r)
32         {
33           cnt++;
34           l=a[i].l,r=a[i].r;
35         }
36       }
37       printf("%d\n",cnt);
38     }
39     return 0;
40 }

Code2