贪心算法

POJ1230总结

Pass-Muraille

题目来源

Description

In modern day magic shows, passing through walls is very popular in which a magician performer passes through several walls in a predesigned stage show. The wall-passer (Pass-Muraille) has a limited wall-passing energy to pass through at most k walls in each wall-passing show. The walls are placed on a grid-like area. An example is shown in Figure 1, where the land is viewed from above. All the walls have unit widths, but different lengths. You may assume that no grid cell belongs to two or more walls. A spectator chooses a column of the grid. Our wall-passer starts from the upper side of the grid and walks along the entire column, passing through every wall in his way to get to the lower side of the grid. If he faces more than k walls when he tries to walk along a column, he would fail presenting a good show. For example, in the wall configuration shown in Figure 1, a wall-passer with k = 3 can pass from the upper side to the lower side choosing any column except column 6.

1230 1


Given a wall-passer with a given energy and a show stage, we want to remove the minimum number of walls from the stage so that our performer can pass through all the walls at any column chosen by spectators.

Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains two integers n (1 <= n <= 100), the number of walls, and k (0 <= k <= 100), the maximum number of walls that the wall-passer can pass through, respectively. After the first line, there are n lines each containing two (x, y) pairs representing coordinates of the two endpoints of a wall. Coordinates are non-negative integers less than or equal to 100. The upper-left of the grid is assumed to have coordinates (0, 0). The second sample test case below corresponds to the land given in Figure 1.

Output

There should be one line per test case containing an integer number which is the minimum number of walls to be removed such that the wall-passer can pass through walls starting from any column on the upper side.

Sample Input

2
3 1
2 0 4 0
0 1 1 1
1 2 2 2
7 3
0 0 3 0
6 1 8 1
2 3 6 3
4 4 6 4
0 5 1 5
5 6 7 6
1 7 3 7

Sample Output

1
1

Hint

Walls are parallel to X.

我的代码

从左向右遍历每一列墙,以检验这一列是否能够穿过。如果不能穿过的就删除这一列中往右侧能达到的最长的一堵墙。证明略。

实现的方式是自己模拟了一个队列,这个队列是按照每一堵墙的最右侧坐标的升序进行的。在遍历第i列时,需要将从i列为起点的墙加进队列,并将最右侧达不到i的墙移出队列。用head和tail来维护就行了。每一次遍历都需要重新对队列进行排序。

for (int i=0;i<=100;i++)
		{
			while(walls[now].begin<=i&&now<n)
			{
				queue[tail++]=walls[now++];
			}
			sort(queue+head,queue+tail);
			while(queue[head].end<i&&head<tail)
			{
				head++;
			}
			while ((tail-head)>k) 
			{
				tail--;
				ans++;
			}
		}

完整代码:

#include<stdio.h>
#include<algorithm>
using namespace std;

struct wall
{
	int begin,end;
	bool operator<(const wall a)const
	{
		return end<a.end;
	}
	
	wall(int begin,int end):begin(begin),end(end){}
	wall(){}
};

bool cmp(wall a,wall b)
{
	return a.begin<b.begin;
}

int main()
{
	int t;
	scanf("%d",&t);
	while (t--)
	{
		int n,k,a,b,temp,ans=0;
		wall walls[10000];
		wall queue[101];
		int tail=0,head=0,now=0;
		scanf("%d%d",&n,&k);
		for (int i=0;i<n;i++)
		{
			scanf("%d%d%d%d",&a,&temp,&b,&temp);
			walls[i].begin=a<b?a:b;
			walls[i].end=a>b?a:b;
		}
		sort(walls,walls+n,cmp);
		for (int i=0;i<=100;i++)
		{
			while(walls[now].begin<=i&&now<n)
			{
				queue[tail++]=walls[now++];
			}
			sort(queue+head,queue+tail);
			while(queue[head].end<i&&head<tail)
			{
				head++;
			}
			while ((tail-head)>k) 
			{
				tail--;
				ans++;
			}
//			printf("checked %d!\n",i); 
		}
		printf("%d\n",ans);
	}
	return 0;
}

反思

这一题原本是想用会场安排的模型来解决的,即优先排满一整个行的墙之后再开始排满下一行,处理完所有的墙之后,选出占有数量最少的一行将其删去。

会场安排问题只关注最小的会场数(行数),但是不关注最少需要去掉几个会议(墙),可能会导致错误的情况的发生:

qq screenshot 20200720131954

利用会场安排问题的算法得到的是上图的结果,这种求法在求最小会场数是极其有效的。但是在这一题中,显然将黄色的墙移动到第二列,并将第一行删去是最好的选择。

发表评论