1303. Minimal Coverage
Time limit: 1.0 second
Memory limit: 64 MB Given set of line segments [Li, Ri] with
integer coordinates of their end points. Your task is to find the minimal subset of the given set which covers segment [0, M] completely (M is a positive integer).
InputFirst line of the input contains an integer M (1 ≤ M ≤ 5000). Subsequent lines of input contain pairs of integers Li and
Ri (?50000 ≤ Li < Ri ≤
50000). Each pair of coordinates is placed on separate line. Numbers in the pair are separated with space. Last line of input data contains a pair of zeroes. The set contains at least one and at most 99999 segments.
OutputYour program should print in the first line of output the power of minimal subset of segments which covers segment [0, M]. The list of segments of covering subset must follow. Format of the list must
be the same as described in input with exception that ending pair of zeroes should not be printed. Segments should be printed in increasing order of their left end point coordinate.
If there is no covering subset then print “No solution” to output.
Samples
Problem Source: II Collegiate Students Urals Programming Contest. Yekaterinburg, April 3-4, 1998
Tags: dynamic programming
)
|
题意：
给很多段 区间的左右端点，以0 0结尾，求最少多少段可以覆盖 0-M。
做法：
贪心就好，先找l小于0中r最大的那一段，然后在把最大的r 做为边界nw，找下一个l<nw中r最大的那一段，不断得找，直到nw超过M跳出。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <list>
struct segment
{
int l,r;
int nxt;
};
segment seg[200100];
int cmp(segment a,segment b)
{
return a.l<b.l;
}
int main()//做节点 升序
{
int m;
while(cin>>m)
{
int n=0;
while(cin>>seg[n].l>>seg[n].r)
{
if(seg[n].l==0&&seg[n].r==0)
break;
n++;
}
sort(seg,seg+n,cmp);
int nw=0;//当前
int zui_r=-999999;
int ans=0;
int nxtid=-1,id=0;
int preid=-1;
int firid=-1;
for(int i=0;i<n;i++)
{
if(seg[i].l<=nw)//边界左
{
if(seg[i].r>zui_r&&(seg[i].r>nw))//更新
{
zui_r=seg[i].r;
//nw=zui_r;
id=i;
}
}
if((seg[i].l>nw||(i==n-1&&zui_r>nw))&&zui_r!=-999999)
{
ans++;
nw=zui_r;
zui_r=-999999;
if(firid==-1)
{
firid=id;
seg[id].nxt=-1;
}
else
{
seg[preid].nxt=id;
seg[id].nxt=-1;
}
preid=id;
if(nw>=m)
break;
i--;
continue;
}
}
if(firid==-1)
{
firid=id;
seg[id].nxt=-1;
}
if(nw<m)
puts("No solution");
else
{
printf("%d\n",ans);
for(int i=firid;~i;i=seg[i].nxt)
{
printf("%d %d\n",seg[i].l,seg[i].r);
}
}
}
return 0;
}URAL 1303. Minimal Coverage 贪心
原文：http://blog.csdn.net/u013532224/article/details/44571821