首页 > 专题系列 > Java解POJ > POJ 1794 Castle Walls [解题报告] Java
2013
11-10

POJ 1794 Castle Walls [解题报告] Java

Castle Walls

问题描述 :

Background

In medieval times, knights commanded big armies of peasants. When they had to storm a castle they would line up neatly in front of the castle’s wall and throw their grappling hooks over the walls. If one does not throw straight it can easily happen that two hooks cross, making it impossible for the two peasants to climb the wall. That’s why every knight made his peasants practice a lot so that this would not happen in combat.

Due to the recent Sir Arthur-Madam Claire Marriage (ACM), two peasant armies have to be merged.

Traditionally Sir Arthur’s peasants wear blue and Madame Claire’s peasants wear red. When practicing together, both armies mix up in front of a castle’s wall. On Sir Arthur’s command, they all throw their grappling hooks. Due to their perfect training the hooks will never cross within an army, however it can happen that a hook thrown by a blue peasant crosses one thrown by a peasant of the red army.

For statistical purposes, Sir Arthur now needs to find out how many grappling hooks have crossed so that he can measure how well their armies have already been merged.

Problem

Given the positions of blue and red peasants as well as the positions they threw their grappling hooks at,determine how many distinct pairs of blue and red peasants crossed their hooks.

If there are n blue and m red peasants, the positions in the line where the peasants are standing are numbered from 1 to n + m. The positions on the castle’s wall are numbered from 1 to n + m as well,where position i is directly opposite of position i on the line the peasants are standing on. A grappling hook thrown from position i to j is said to cross another hook thrown from k to l if and only if

(i < k and j >= l) or (i > k and j <= l)

Grappling hooks of the same color will never cross each other, nor will two peasants occupy the same position on the line. However, two hooks (of different color) can be thrown to the same position in which case they are said to cross each other as well.

输入:

The first line contains the number of scenarios.

In each scenario, you are first given a line with two integers n and m, the number of blue and red peasants, respectively (1 <= n,m <= 30 000).

The next n lines describe the blue peasants followed by m more lines for the red peasants. Each line consists of two integer i and j separated by a space, indicating the peasant’s position i and the position j he threw his grappling hook to (1 <= i, j <= n + m).

输出:

For each scenario first output a line “Scenario #i:” where i is the number of the scenario starting with 1, followed by a line containing the number of distinct pairs of peasants whose grappling hooks are crossed,and print a blank line at the end of each scenario.

样例输入:

2
2 2
1 2
3 4
2 1
4 3
2 3
1 3
2 5
5 3
3 1
4 2

样例输出:

Scenario #1:
2

Scenario #2:
6

解题代码:

/* @author: */
import java.util.Scanner;
public class Main {


  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int cas, k;
    cas=sc.nextInt();
    for( k=1; k<=cas; k++ )
    {
       int s1[]=new int[60010], s2[]=new int[60010];
     	int i, n, m, a, b, ans;

	n=sc.nextInt();
       m=sc.nextInt();
	
	for( i=0; i< n; i++ )
	{
          a=sc.nextInt();
          b=sc.nextInt();
	   s1[a]++;
	   s2[b]++;
	}

	for( i=1; i<=n+m; i++ ){
	   s1[i] += s1[i-1];
          s2[i] += s2[i-1];
       }

	ans = 0;
	for( i=0; i< m; i++ )
	{
          a=sc.nextInt();
          b=sc.nextInt();
	   if( s1[a] >= s2[b] )
		ans += s1[a] - s2[b-1];
	   else
		ans += s2[b] - s1[a];
	}

	System.out.printf( "Scenario #%d:\n", k );
	System.out.printf( "%d\n\n", ans );
   }

 }
}

  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks