学步园

题目大意：给你一些线段的起止点，问你最少用多少条线段可以把一段区间覆盖 线段数<=25000 区间<=1000000

1、spfa+离散化+SLF即可，直接上代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
const int maxn=1000010,maxm=2000010;
using namespace std;
int st,ed,tot=0;
int f[maxn],now[maxn];
bool b[maxn];
int h[maxm];
int pre[maxm],son[maxm],v[maxm];

inline void cc(int a,int b,int c)
{
	pre[++tot]=now[a];
	now[a]=tot;
	son[tot]=b;
	v[tot]=c;
}

inline int read()
{
    char ch; int tmp=0;
    while(ch=getchar()) if('0'<=ch && ch<='9') break;
    for(;'0'<=ch && ch<='9';ch=getchar()) tmp=tmp*10+ch-'0';
    return tmp;
}
int a[50010];
inline void init()
{
	int n=read();
	st=1;
	ed=read()+1;
	for (int i=1;i<=n;i++)
		{
			int l=read();
			int r=read()+1;
			cc(l,r,1);
			a[n+i]=r;
			a[i]=l;
		}
	sort(a+1,a+2*n+1);
	for (int i=2;i<=2*n;i++)
		cc(a[i],a[i-1],0);
}

inline void spfa()
{
	memset(f,63,sizeof(f));
	int t=0,w=1;
	f[st]=0;
	h[1]=st;
	b[st]=1;
	while (t!=w)
		{
			if (++t==maxn) t=1;
			int p=now[h[t]];
			while (p)
				{
					if (f[h[t]]+v[p]<f[son[p]] && f[h[t]]+v[p]<f[ed])
						{
							f[son[p]]=f[h[t]]+v[p];
							if (!b[son[p]])
								{
									b[son[p]]=1;
									if (++w==maxn) w=1;
									h[w]=son[p];
									int tt=t+1==maxn?1:t+1;
									if (f[h[tt]]>f[h[w]])
										swap(h[tt],h[w]);
								}
						}
					p=pre[p];
				}
			b[h[t]]=0;
	}
	if (f[ed]>1000000) f[ed]=-1;
	printf("%d",f[ed]);
}

int main()
{
	init();
	spfa();
	return 0;
}

2、dp，先按线段右端点排序，然后线段树优化之，代码没写

3、贪心，先按左段点排序，找到最靠右的右端点即可，贴代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
using namespace std;
int getint(){
	int sym=1;
	int res=0; char ch;
	while(!isdigit(ch=getchar())) if(ch=='-') sym=-1;
	res=ch-'0';
	while(isdigit(ch=getchar())) res=res*10+ch-'0';
	return sym*res;
}
void putint(int x){
	if(x<0) putchar('-'),x=-x;
	if(x>=10) putint(x/10);
	putchar(x%10+'0');
}

const int maxn=25010;
typedef pair<int,int> PII;
PII seg[maxn];
int n,m;

bool cmp_l(const PII &a,const PII &b){
	return a.first<b.first || a.first==b.first && a.second>b.second;
}
void init(){
	n=getint(),m=getint();
	for(int i=1;i<=n;++i)
		seg[i].first=getint()-1,seg[i].second=getint();
	sort(seg+1,seg+n+1,cmp_l);
	seg[n+1]=make_pair(m,m);
}

int min_seg(){
	if(seg[1].first>1) return -1;
	int maxr=0,ans=0;
	for(int i=1,nowr=0;i<=n+1 && maxr<m;++i){
		if(seg[i].first<=maxr){ nowr=max(nowr,seg[i].second); continue; }
		maxr=nowr; if(seg[i].first>maxr) return -1;
		++ans,nowr=seg[i].second;
	}
	if(maxr<m) return -1; return ans;
}

int main(){
	init();
	printf("%d\n",min_seg());
	return 0;
}