首页 > 专题系列 > Java解POJ > POJ 1230 Pass-Muraille [解题报告] Java
2013
11-09

POJ 1230 Pass-Muraille [解题报告] Java

Pass-Muraille

问题描述 :

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.



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.

输入:

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.

输出:

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.

样例输入:

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

样例输出:

1
1

温馨提示:

Walls are parallel to X.

解题代码:

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;
interface Pass{
	int N = 100+10;
	void SetInit(int n,int k);
	void AddData(int left,int right);
	void InitData();
	int GetAns();
}
class Interval implements Comparable{
	int left,right;
	void set(int left,int right){
		this.left = left;
		this.right = right;
	}
	public int compareTo(Object obj){
		Interval temp = (Interval)obj;
		if(this.right>temp.right) return 1;
		return -1;
	}
}
class Muraille implements Pass{
	
	int n,k,cnt;
	int Graph[] = new int[N];
	int select[] = new int[N];
	Interval wall[] = new Interval[N];
	Muraille(){
		for(int i=0;i< N;++i) wall[i] = new Interval();
	}
	public void SetInit(int n,int k){
		cnt = 0;
		this.n = n;
		this.k = k;
		Arrays.fill(Graph, 0);
	}
	public void AddData(int left,int right){
		wall[cnt].set(left, right);
		for(int i=left;i<=right;++i){
			++Graph[i];
		}
		++cnt;
	}
	public void InitData(){
		Arrays.sort(wall,0,n);
	}
	void delete(int who){
		for(int i=wall[who].left;i<=wall[who].right;++i){
			--Graph[i];
		}
		wall[who].right = -1;
	}
	void delete(int left,int num){
		for(int i=n-1;i>=0 && num>0;--i) if(wall[i].left<=left && wall[i].right!=-1){
			--num;
			delete(i);
		}
	}
	public int GetAns(){
		int ans=0;
		for(int i=0;i< N;++i){
			if(Graph[i]>k){
				ans+=Graph[i]-k;
				delete(i,Graph[i]-k);
			}
		}
		return ans;
	}
	
}
public class Main {
 public static void main(String[]args)throws Exception{
	int Test,n,k;
	Muraille muraille = new Muraille();
	StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
	Test = GetNum(cin);
	while(Test--!=0){
        n = GetNum(cin);
	 k = GetNum(cin);
	 muraille.SetInit(n,k);
	 for(int i=0;i< n;++i){
		int left = GetNum(cin);
		GetNum(cin);
		int right = GetNum(cin);
		GetNum(cin);
		if(left>right) muraille.AddData(right, left);
		else muraille.AddData(left, right);
	}
	
	muraille.InitData();
	System.out.println(muraille.GetAns());
  }
 }
	static int GetNum(StreamTokenizer cin)throws Exception{
		cin.nextToken();
		return (int) cin.nval;
	}
}

  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示