本文共 1455 字，大约阅读时间需要 4 分钟。
链接：
http://acm.timus.ru/problem.aspx?space=1&num=1303
按照贪心的思想，每次找到覆盖要求区间左端点时，右端点最大的线段，然后把要求覆盖的区间改为这个右端点到M这个区间。依次类推下去，这样的话就只需要扫一遍就可以找去来。
要做的预备工作就是将线段按照左端点的升序排序就可以了。
它的时间复杂度就是O(n)
代码一直WA，望大神指教
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 using namespace std;13 #define MAX(a,b) (a > b ? a : b)14 #define MIN(a,b) (a < b ? a : b)15 #define MAXN 20000516 #define INF 100000000717 #define mem(a) memset(a,0,sizeof(a))18 #define judge(i) (ma[i].l<=L && ma[i].r>=L && ma[i].l != ma[i].r)//判断是否覆盖了点L19 20 struct node{ int l,r;}ma[MAXN];21 int ans[MAXN];22 int M,N,T;23 int L;24 25 int cmp(node a,node b)26 {27 if(a.l != b.l)return a.l endd)41 {42 endd = ma[i].r;43 e = i;44 }45 i++;46 }47 L = endd;//endd就是满足覆盖条件下的最大的右端点48 //并将其设置为下次比较的左端点49 return e;//返回此次的线段的下标50 }51 52 int main()53 {54 while(~scanf("%d",&M))55 {56 N=0;57 int i;58 mem(ans);59 while(scanf("%d%d",&ma[N].l, &ma[N].r) && (ma[N].l || ma[N].r))60 {61 if(ma[N].r <=0 || ma[N].l>=M)ma[N].l = ma[N].r = INF;//吧在要求区间两端之外的线段去掉62 //吧它的左右端点值赋值为INF，这样的话排序时自然就会到最后方，也就相当于不用考虑63 N++;64 }65 sort(ma,ma+N,cmp);66 67 L = 0;//最初要被覆盖的点是068 int num = 0;69 for(i=0;i = M)break;//一旦找到，就退出循环75 }76 if(L < M)printf("No solution\n");77 else78 {79 printf("%d\n",num);80 for(i=0;i
转载于:https://www.cnblogs.com/gj-Acit/p/3207666.html