贪心专题-区间问题

自用笔记算法

贪心专题-区间问题

HDU 1050

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

有两排房间 中间是走廊 需要在房间中移动桌子 走廊都是只能使一个桌子移动 问在所给的房间移动桌子最少需要多少时间（次数*10）

参考AC代码(贪心正解)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <algorithm>
using namespace std;
struct node
{
	int a,b;
	bool flag;
}room[500];
bool cmp(node x1,node x2)    //区间左端点升序排列
{
	return x1.a<x2.a;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int t;
	cin>>t;
	while(t--)
	{
		int n;
		cin>>n;
		for(int i=0;i<n;i++)
		{
			cin>>room[i].a>>room[i].b;
			if(room[i].a>room[i].b)
				swap(room[i].a,room[i].b);   //保证区间左端点小 右端点大
			if(!room[i].a&1)                 //左端点保证是奇数
				room[i].a--;                 //上操作和下操作是因为存在共用一个走廊的情况 如13和46变为14和36 其实区间相交
			if(room[i].b&1)                  //右端点保证是偶数
				room[i].b++;
			room[i].flag=false;              //每个房间初始化为false表示未访问
		}
		sort(room,room+n,cmp);               //贪心 左端点排序
		int count=-1,preb;
		bool ex=true;
		while(ex)                            //核心 每次尽可能移动到不相交区间的最右端
		{
			count++;
			ex=false;
			preb=0;                          //每次进行循环时preb需要清零
			for(int i=0;i<n;i++)
			{
				if(!room[i].flag&&room[i].a>preb)  //若存在下一个区间与前一个区间不相交 那么改变preb的值 继续右移
				{
					room[i].flag=true;           //访问过的区间不能再访问
					ex=true;                     //只要能找到这样的区间 继续进入while循环
					preb=room[i].b;
				}
			}
		}
		cout<<count*10<<endl;
	}
	return 0;
}

参考AC代码（暴力）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int room[500];
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int t;
	cin>>t;
	while(t--)
	{
		memset(room,0,sizeof(room));      //用room数组存放每个房间重叠的次数
		int n;                            //最后遍历room求出重叠最多的次数*10即为答案
		cin>>n;                           //房间数很大时不能使用 此方法是用空间换时间 鉴于此题只有400个房间所以可以使用
		for(int i=0;i<n;i++)
		{
			int a,b;
			cin>>a>>b;
			if(a>b)
				swap(a,b);
			if(!a&1)
				a--;
			if(b&1)
				b++;
			for(int i=a;i<=b;i++)
				room[i]++;
		}
		int ans=room[0];
		for(int i=1;i<400;i++)
			ans=max(ans,room[i]);
		cout<<ans*10<<endl;
	}
	return 0;
}

HDU 2037

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<iostream>
#include<algorithm>
using namespace std;
struct node
{
	int a,b;
}num[150];
bool cmp(node x,node y)
{
	return x.b<y.b;
}
int main()                     //选择最大不相交区间问题
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	while(cin>>n)
	{
		if(n==0)
			break;
		for(int i=1;i<=n;i++)
			cin>>num[i].a>>num[i].b;
		sort(num+1,num+1+n,cmp);        //按照右端点b升序排列 选择第一个区间
		int ans=1;                      //删除和第一个区间相交的区间 继续选择第一个 以此类推
		int limit=num[1].b;
		for(int i=2;i<=n;i++)
		{
			if(num[i].a>=limit)
			{
				ans++;
				limit=num[i].b;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

HDU 5696

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100005;
#define LL long long 
int a[maxn];
LL ans[maxn];
void dfs(int low,int high)        //类似于快排的思想 枢轴为最小值
{
	if(low>high)
		return;
	if(low==high)               //low==high说明搜索到只有一个数 返回自己的平方作为一个数做区间的值
	{
		ans[1]=max(ans[1],1ll*a[low]*a[low]);
		return;
	}
	int maxi=low,mini=low;
	for(int i=low;i<=high;i++)      //找出最大值和最小值的位置
	{
		if(a[i]>a[maxi])
			maxi=i;
		if(a[i]<a[mini])
			mini=i;
	}
	ans[high-low+1]=max(ans[high-low+1],1ll*a[maxi]*a[mini]);   //把区间长度的价值（max*min）算出
	dfs(low,mini-1);                   //以最小值作为枢轴向左和右搜索
	dfs(mini+1,high);
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	while(scanf("%d",&n)!=EOF)
	{
		for(int i=1;i<=n;i++)
		{	scanf("%d",&a[i]);
			ans[i]=0;
		}
		dfs(1,n);
		for(int i=n-1;i>=1;i--)         //dfs后有的区间未计算 通过和上一个区间求最大值算出
			ans[i]=max(ans[i],ans[i+1]);
		for(int i=1;i<=n;i++)
			printf("%I64d\n",ans[i]);
	}
	return 0;
}

HDU 2158

Problem Description

Input

Output

Sample Input

Sample Output

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<iostream>
#include<cstring>
using namespace std;
const int maxn=100000+50;
int data[maxn],num[maxn],mark[maxn],pos[maxn];
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n,m;
	while(cin>>n>>m)
	{
		if(n==0&&m==0)
			break;
		memset(pos,-1,sizeof(pos));
		memset(mark,0,sizeof(mark));
		for(int i=0;i<n;i++)        //在输入数据的同时用pos数组算出每个数字第一次出现的位置
		{	
			cin>>data[i];
			if(pos[data[i]]==-1)
				pos[data[i]]=i;
		}
		for(int i=1;i<=m;i++)        //对于每次询问 r，l，num一定要初始化
		{
			int r=-1,l=n;
			memset(num,0,sizeof(num));
			int que_num;
			cin>>que_num;
			for(int j=0;j<que_num;j++)
			{
				int q;
				cin>>q;
				mark[q]=i;           //询问的数字用mark来与未询问的数字区别开
				if(pos[q]>r)         //根据pos与r，l的关系求出第一个最基本的包含询问值的区间
					r=pos[q];
				if(pos[q]<l)
					l=pos[q];
			}
			for(int j=l;j<=r;j++)     //用num数组保存这个最基本区间中每个数字出现的次数
				num[data[j]]++;
			int maxlen=r-l+1;         //最基本区间的大小
			while(r<n)                //贪心 向右不停的遍历l 同时维护r 使整个区间内仍满足存在m个访问数
			{
				num[data[l]]--;
				if(num[data[l]]==0)           //若某个减少到0 那么l右移 同时维护r 同时右移
				{
					while(++r<n&&data[l]!=data[r])         //只要r处的值不等于原来l处的值 一直右移 同时此区间数字的个数+1
						num[data[r]]++;
					num[data[r]]=1;                  //直到找到l处删减的数字 该数字初始化为1
				}
				while(++l<=r&&mark[data[l]]!=i);       //l右移时候通过mark数组直接访问下一个需要查询的数字 跳过无需查询的数字
				if(r<n&&r-l+1<maxlen)            //若此时的区间小于maxlen 更新maxlen
					maxlen=r-l+1;                 
			}                                    //整个过程需满足r＜n l≤r
			cout<<maxlen<<endl;
		}
	}
	return 0;
}

广工业新生赛E-穷游中国在统题

Problem Description
Travel_poorly队是广工大目前最年轻的金牌队伍，队内成员分别是tmk、YFQ、Maple。这天他们接到教练的order要给新生杯统题，统题是个不轻松的工作,
要评估各个题目的难度，设计出一套有梯度的套题，使得做题的情况有区分度。tmk很快想出了解决的办法，他给每道题目都设置了一个难度值，然后按照
难度值进行筛选题目，这时候他发现难度值刚开始有可能是无序的，于是他决定要让全部题目都按照难度值从小到大排好序。 这时候YFQ说让他来排序，
排序是一个展现算法魅力的过程，他要通过一种有趣的方法来给题目的难度值排序： 首先他把题目划分成很多组，每组的题目都是连续的，例如某一组包
含从i到j的题目，那么这一组包含的是第i，i+1，i+2，i+3，…，j题。 这样每道题都属于某一个组，然后他再到组内把题目按照难度值进行从小到大排
序。 当每个组内都进行排序之后，最终全部题目的难度值将按照从小到大的顺序排列好。 我们知道每一组里面的题目越多，排序的压力就越大，所以
Maple提出一个合理的要求，就是让每个组里面的题目数量尽可能的少，聪明的ACMer，你知道Travel_poorly一共要分出多少个组吗？

Input
第一行是一个整数t ( t<= 10 )，表示有t组数据。在每组数据中： 第一行是一个整数n ( n<=1000 00 )，表示题目的总数； 第二行是n个整数A1,A2,A3
…An ( 0<=Ai<= 1000 000 000)，表示每道题目的难度值

Output
对于每组数据，输出一个正整数，表示一共要分出多少个组能满足Travel_poorly的要求，每两组样例之间输出一个空行。

Sample Input
2
5
3 2 5 4 6
5
5 4 3 2 1

Sample Output
3

1

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <cstring>
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int num[1111111];
int f[1111111];
struct node
{
	int x,id;
}a[1111111];
int main()
{
	int T,n;
	cin>>T;
	while(T--)
	{
		memset(f,0,sizeof(f));
		memset(num,0,sizeof(num));
		scanf("%d",&n);
		for(int i=1;i<=n;i++)
			scanf("%d",&num[i]);
		for(int i=1;i<=n;i++)
		{
			a[i].x=num[i];
			a[i].id=i;
		}
		f[n]=num[n];
		for(int i=n-1;i>=1;i--)    //通过遍历数组实现f存放窗为2的最小值
		{                          //数组f最后一位存放的是最后一个数字
			f[i]=num[i];
			f[i]=min(f[i],f[i+1]);
		}	
		int ans=1,mx=-INT_MAX;
        for(int i=1;i<=n;i++)       //同时mx求出前i个数字的最大值
		{
            mx=max(mx,num[i]);
			/*cout<<mx<<endl;*/
            if(f[i+1]>=mx) ans++;    //若前i个数的最大值小于后2个数（窗为2 f数组已计算）的最小值
        }                            //说明这2个区间不可能合并 为了使每个区间尽可能小 需要把这2个区间分开 ans++
		printf("%d\n",ans);
		if(T!=0)puts("");
	}
	return 0;
}

简单图解

以第一个输入为例（3 2 5 4 6）
（3）（2 5）4 6
max=3 min=5
（3 2）|（5 4）6
max=3 min=4 说明两区间不可能合并 ans++
（3 2 5）（4 6）
max=5 min=4
（3 2|5 4）| 6
max=5 min=6 说明前区间和6不可能合并 ans++

HDU 2476

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

区间dp
每次可以把一个区间内的字母统一更新为新的字母 问最少经过多少次更新上式可以变为下式

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<algorithm>
#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int dp[150][150],ans[150];     //dp[i][j]表示区间i-j刷的方法数
string s1,s2;                  //ans表示0到len-1的方法数
int main()
{
	/*freopen("input.txt","r",stdin);*/
	while(cin>>s1>>s2)
	{
		memset(dp,0,sizeof(dp));
		int len=s1.size();
		for(int j=0;j<len;j++)
		{
			for(int i=j;i>=0;i--)        //区间i到j
			{
				dp[i][j]=dp[i+1][j]+1;    //先每个单独刷 初始化
				for(int k=i+1;k<=j;k++)
				{
					if(s2[k]==s2[i])      //若k与i处的值相等 把区间s2分成两个部分预处理
						dp[i][j]=min(dp[i][j],dp[i+1][k]+dp[k+1][j]);
				}
			}
		}
		for(int i=0;i<len;i++)          //根据ans的定义把ans初始化
			ans[i]=dp[0][i];
		for(int j=0;j<len;j++)
		{
			if(s1[j]==s2[j])           //如果某个位置s1和s2相等 那么该位置不用刷 等于上一位置j-1的值
				ans[j]=ans[j-1];
			else                       //若不相等 利用区间分割 分别求0-i i+1-j的和
			{
				for(int i=0;i<j;i++)
					ans[j]=min(ans[j],(ans[i]+dp[i+1][j]));
			}
		}
		cout<<ans[len-1]<<endl;
	}
	return 0;
}

POJ 1328

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

x轴上方是海 下方是陆地 给出一些点的坐标代表岛屿 问在陆地上最少需要建造多少半径已给出的雷达可以覆盖所有的岛屿

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<iostream>
#include<cstring>
#include<math.h>
#include<algorithm>
#define maxn 1005
using namespace std;
struct Node
{
	float a,b;
}node[maxn];
bool cmp(Node x,Node y)       //贪心左端点
{
	return x.a<y.a;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n;
	float r;
	int count=1;
	while(cin>>n>>r)
	{
		if(n==0&&r==0)
			break;
		int flag=0;
		/*if(r<0)              //亲测 不需要判断半径是否小于0 仍可AC
			flag=1;*/
		for(int i=0;i<n;i++)
		{
			float x,y;        //圆的坐标 半径用float或double
			cin>>x>>y;
			if(abs(y)>r)      //只要有一个圆与x轴无交点 输出-1
				flag=1;
			else
			{
				node[i].a=-sqrt(r*r-y*y)+x;   //保存圆与x轴的左右交点
				node[i].b=sqrt(r*r-y*y)+x;
			}
			/*cout<<node[i].a<<" "<<node[i].b<<endl;*/
		}
		cout<<"Case "<<count++<<": ";
		if(flag==1)
		{
			cout<<"-1"<<endl;
			continue;
		}
		sort(node,node+n,cmp);
		int ans=1;
		float limit=node[0].b;    //注意：中间值一定不能写成int WA数次
		for(int i=1;i<n;i++)
		{
			if(node[i].a>limit)        //若两区间无交点 需+1 右上限更新
			{
				ans++;
				limit=node[i].b;
			}
			else if(node[i].b<limit)      //若新区间的右上限小于旧区间的右上限 更新limit
				limit=node[i].b;
		}
		cout<<ans<<endl;
	}
	return 0;
}

POJ 3485

Problem Description

Input

Output

Sample Input

Sample Output

题目要去

与上题类似 在上题的基础上给定的道路有上限 为0-t 在考虑圆与x轴的交点时预处理下即可

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
struct Node
{
	double a,b;
}node[10050];
bool cmp(Node x,Node y)
{
	if(x.b==y.b)
		return x.a>y.a;
	else
		return x.b<y.b;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	double l;
	while(cin>>l)
	{
		double r;
		cin>>r;
		int n;
		cin>>n;
		int flag=0;
		if(l<=0||r<=0)
			flag=1;
		for(int i=0;i<n;i++)
		{
			double x,y;
			cin>>x>>y;
			if(y-r>0)
				flag=1;
			node[i].a=x-sqrt(r*r-y*y);
			if(node[i].a<0)             //与上题类似 只需注意区间范围在0-l 若超出范围 更新为上下界
				node[i].a=0;
			node[i].b=x+sqrt(r*r-y*y);
			if(node[i].b>l)
				node[i].b=l;
		}
		if(flag==1)
		{
			cout<<'0'<<endl;
			continue;
		}
		sort(node,node+n,cmp);
		int ans=1;
		double limit=node[0].b;
		for(int i=1;i<n;i++)
		{
			if(node[i].a>limit)
			{
				limit=node[i].b;
				ans++;
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

与上题对比

都是同一类区间重复问题
但是采用的分别是对左端点排序和右端点排序的两种方法
若对左端点排序 那么for循环里需要进行两步判断
若对右端点排序 那么for循环里只需要一步判断即可

POJ 2376

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

区间覆盖问题 给定一个大区间和若干小区间 求用最少数量的小区间把大区间覆盖 若不能覆盖输出-1

参考AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<iostream>
#include<algorithm>
using namespace std;
struct Node
{
	int a,b;
}node[25555];
bool cmp(Node x,Node y)    //优先左端点升序排列
{
	if(x.a==y.a)
		return x.b>y.b;
	else
		return x.a<y.a;
}
int main()
{
	/*freopen("input.txt","r",stdin);*/
	int n,t;
	while(cin>>n>>t)
	{
		for(int i=0;i<n;i++)
		{
			cin>>node[i].a>>node[i].b;
			if(node[i].a<1)           //预处理 所有不在1-t的范围都应更新到这个范围内
				node[i].a=1;
			if(node[i].b>t)
				node[i].b=t;
		}
		sort(node,node+n,cmp);
		int ans=1;
		if(node[0].a>1)                //若第一个区间的起点不是1 那么输出-1 后面的起点一定大于1
		{
			cout<<"-1"<<endl;
			continue;
		}
		int id=0;                   //id相当于主区间 后面所有合理的区间都与他比较 id每次都是跳到下一个最远区间的位置
		for(int i = 0; i < n; )
		{  
			int cnt = 0;            //cnt用来记录每一轮与主区间比较时最远区间的位置
			for(int j = i + 1; j < n; ++j)
			{  
				if(node[j].a > node[id].b + 1)     //若存在区间的左端点比上一个区间的右端点+1还要大 直接break 后面的区间由于左端点排过序 都不满足
					break;                         //本题需注意1-5 6-10也是合理的区间
				if(node[j].b >= node[id].b + 1)    //每次要比较的区间的右端点需要比主区间的右端点大至少1 才能满足这次的更新有意义（至少后移1）
				{  
					if(node[j].b > node[cnt].b)    //满足上述条件后找出所有满足该条件的走的最远的位置 置为cnt
						cnt = j;                   //cnt置0可以使主区间更新后的下一个满足上述条件的区间作为最大值的区间 置为cnt
				}                                  
			}  
			if(cnt == 0)                           //若cnt==0说明该区间被主区间所包含 此区间不要 i++
				i++;   
			else                                   //若找到了最远的区间 ans++ id和i直接跳到最远区间的位置 以此为基准开始做后面区间的判断
			{  
				id = cnt;  
				ans++;  
				i = id;  
			}  
		}
		if(node[id].b==t)      //走到最后的右区间达到t 满足输出ans
			cout<<ans<<endl;
		else                  //未到达说明不满足输出-1
			cout<<"-1"<<endl;
	}
	return 0;
}

注意点

本人对for循环主体做了微调 但却超时
调整再与cnt不用每次更新 而是等于i 这样每次在进行下一轮比较时候初始化最大区间就是自己 if语句里需改成cnt==i
同时也不需要两步if叠加 值需要下一部即可 给出代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int id=0,cnt=0;                   
		for(int i = 0; i < n; )
		{           
			for(int j = i + 1; j < n; ++j)
			{  
				if(node[j].a > node[id].b + 1)     
					break;                         
				if(node[j].b > node[cnt].b)    
					cnt = j;                                                  
			}  
			if(cnt == i)                           
				i++;   
			else                                  
			{  
				id = cnt;  
				ans++;  
				i = id;  
			}  
		}

但却超时 所以提供的代码还是每轮cnt=0的情况

本文标题:贪心专题-区间问题

文章作者:Hippopmonkey

发布时间:2017-02-03, 20:44:01

最后更新:2017-02-04, 18:58:21

原始链接:http://xuboming8.github.io/2017/02/03/贪心专题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 贪心专题-区间问题
    1. 1.1. HDU 1050
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码(贪心正解)
      3. 1.1.3. 参考AC代码（暴力）
    2. 1.2. HDU 2037
      1. 1.2.1. 参考AC代码
    3. 1.3. HDU 5696
      1. 1.3.1. 参考AC代码
    4. 1.4. HDU 2158
      1. 1.4.1. 参考AC代码
    5. 1.5. 广工业新生赛E-穷游中国在统题
      1. 1.5.1. 参考AC代码
      2. 1.5.2. 简单图解
    6. 1.6. HDU 2476
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
    7. 1.7. POJ 1328
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码
    8. 1.8. POJ 3485
      1. 1.8.1. 题目要去
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 与上题对比
    9. 1.9. POJ 2376
      1. 1.9.1. 题目要求
      2. 1.9.2. 参考AC代码
      3. 1.9.3. 注意点
|