本文共 3403 字，大约阅读时间需要 11 分钟。

原题链接：

一：原题内容

Description

Input

Output

Sample Input

43 62 40 24 7

Sample Output

4

二：分析理解

题意：给出数轴上的n个区间，每个区间都是连续的int区间。

现在要在数轴上任意取一堆元素，构成一个元素集合V 要求每个区间和元素集合V的交集至少有两个不同的元素 求集合V最小的元素个数。 设s[x] = 从0 到x 的所有在题意要求的集合中的数的个数 则ai到bi的个数即S[bi] - S[ai-1]。 因此有 (1) S[bi] - S[ai-1] >= 2。 又根据s[x]本身的性质， 后面的一定不比前面的小，后面的最多比前面多一，有： (2)  s[i + 1] - s[i] >= 0 (3)  s[i + 1] - s[i] <= 1

因此我们一共有三个关系式：

S[bi] - S[ai-1] >= 2 s[i + 1] - s[i] >= 0 s[i] - s[i + 1] >= -1 这里需要注意的是三个关系式都是大于等于，因为此题要求求出最小值，并不是最大值，和其他的题有区别。

三：AC代码

#include
   
      #include
    
     #include
     
      using namespace std;struct Edge{	int v;//箭头指向的位置，在此不存储u节点	int dis;//边的距离，也就是权值	int next;//持有同一个u的下一个边};Edge edge[40005];int head[10005];int dis[10005];int sta[40005];bool visited[10005];int n;int a, b;int num;void AddEdge(int u, int v, int w){	edge[num].dis = w;	edge[num].v = v;	edge[num].next = head[u];	head[u] = num++;}void Spfa(int s){	memset(dis, -1, sizeof(dis));	dis[s] = 0;	int top = 1;	visited[s] = 1;	sta[top] = s;	while (top)	{		int u = sta[top--];		visited[u] = 0;		for (int i = head[u]; i != -1; i = edge[i].next)		{			int v = edge[i].v;			if (dis[v] < dis[u] + edge[i].dis)			{				dis[v] = dis[u] + edge[i].dis;				if (!visited[v])				{					sta[++top] = v;					visited[v] = 1;				}			}		}	}}int main(){	scanf("%d", &n);	num = 0;	fill(head, head + 10005, -1);	int maxx = -1;	for (int i = 0; i < n; i++)	{		scanf("%d%d", &a, &b);		AddEdge(a, b + 1, 2);		maxx = max(maxx, b + 1);	}	for (int i = 0; i < maxx; i++)//需要定义四倍的数组。。。	{		AddEdge(i, i + 1, 0);		AddEdge(i + 1, i, -1);		AddEdge(maxx + 2, i, 0);	}	Spfa(maxx + 2);	printf("%d\n", dis[maxx]);	return 0;}
     
    
   

#include
   
        #include
    
       #include
     
        using namespace std;struct Edge{	int v;//箭头指向的位置，在此不存储u节点  	int dis;//边的距离，也就是权值  	int next;//持有同一个u的下一个边  };Edge edge[40005];int head[10005];int dis[10005];int sta[40005];bool visited[10005];int n;int a, b;int num;void AddEdge(int u, int v, int w){	edge[num].dis = w;	edge[num].v = v;	edge[num].next = head[u];	head[u] = num++;}void Spfa(int s){	memset(dis, -1, sizeof(dis));	dis[s] = 0;	int top = 1;	visited[s] = 1;	sta[top] = s;	while (top)	{		int u = sta[top--];		visited[u] = 0;		for (int i = head[u]; i != -1; i = edge[i].next)		{			int v = edge[i].v;			if (dis[v] < dis[u] + edge[i].dis)			{				dis[v] = dis[u] + edge[i].dis;				if (!visited[v])				{					sta[++top] = v;					visited[v] = 1;				}			}		}	}}int main(){	scanf("%d", &n);	num = 0;	fill(head, head + 10005, -1);	int maxx = -1;	int minn = 99999999;	for (int i = 0; i < n; i++)	{		scanf("%d%d", &a, &b);		AddEdge(a, b + 1, 2);		maxx = max(maxx, b + 1);		minn = min(minn, a);	}	for (int i = minn; i < maxx; i++)//需要定义四倍的数组。。。  	{		AddEdge(i, i + 1, 0);		AddEdge(i + 1, i, -1);		//AddEdge(maxx + 2, i, 0);	}	Spfa(minn);	printf("%d\n", dis[maxx]);	return 0;}
     
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51030335 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！