首页 > 专题系列 > Java解POJ > POJ 1975 Median Weight Bead [解题报告] Java
2013
11-10

POJ 1975 Median Weight Bead [解题报告] Java

Median Weight Bead

问题描述 :

There are N beads which of the same shape and size, but with different weights. N is an odd number and the beads are labeled as 1, 2, …, N. Your task is to find the bead whose weight is median (the ((N+1)/2)th among all beads). The following comparison has been performed on some pairs of beads:

A scale is given to compare the weights of beads. We can determine which one is heavier than the other between two beads. As the result, we now know that some beads are heavier than others. We are going to remove some beads which cannot have the medium weight.

For example, the following results show which bead is heavier after M comparisons where M=4 and N=5.

1.	Bead 2 is heavier than Bead 1.

2. Bead 4 is heavier than Bead 3.
3. Bead 5 is heavier than Bead 1.
4. Bead 4 is heavier than Bead 2.

From the above results, though we cannot determine exactly which is the median bead, we know that Bead 1 and Bead 4 can never have the median weight: Beads 2, 4, 5 are heavier than Bead 1, and Beads 1, 2, 3 are lighter than Bead 4. Therefore, we can remove these two beads.

Write a program to count the number of beads which cannot have the median weight.

输入:

The first line of the input file contains a single integer t (1 <= t <= 11), the number of test cases, followed by the input data for each test case. The input for each test case will be as follows:

The first line of input data contains an integer N (1 <= N <= 99) denoting the number of beads, and M denoting the number of pairs of beads compared. In each of the next M lines, two numbers are given where the first bead is heavier than the second bead.

输出:

There should be one line per test case. Print the number of beads which can never have the medium weight.

样例输入:

1
5 4
2 1
4 3
5 1
4 2

样例输出:

2

解题代码:

import java.util.Scanner;
public class Main {

/**
* @param args
*/
static final int max=100;
//static final int inf=1000000000;
static int mapstrstr[][];
public static void main(String[] args) {
   // TODO Auto-generated method stub
   Scanner sc=new Scanner(System.in);
   int t,x,y,z,m,n;
   mapstrstr=new int[max][max];
   t=sc.nextInt();
   for(int i0=0;i0< t;i0++)
   {
    n=sc.nextInt();
    m=sc.nextInt();
    for(int j=1;j<=n;j++)
    {
     for(int l=j+1;l<=n;l++)
     {
      mapstrstr[j][l]=mapstrstr[l][j]=100000;
     }
     mapstrstr[j][j]=100000;
    }
    for(int j=1;j<=m;j++)
    {
     int temp1=sc.nextInt();
     int temp2=sc.nextInt();
     mapstrstr[temp1][temp2]=1;
    }
    for(int k=1;k<=n;k++)
     for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
      {
       if(mapstrstr[i][j]>mapstrstr[i][k]+mapstrstr[k][j])
       mapstrstr[i][j]=mapstrstr[i][k]+mapstrstr[k][j];
      }
      //System.out.println(mapstrstr[4][1]);
      /*
    for(int i=1;i<=n;i++)
    {
   
    for(int j=1;j<=n;j++)
    {
    System.out.print(mapstrstr[i][j]+" ");
    
    }
    System.out.println("");
    }
    */
    z=0;
    for(int i=1;i<=n;i++)
    {x=y=0;
     for(int j=1;j<=n;j++)
      if(mapstrstr[i][j]!=100000)x++;
     for(int j=1;j<=n;j++)
      if(mapstrstr[j][i]!=100000)y++;
     if(x>=(n+1)/2||y>=(n+1)/2)z++;
    }
    System.out.println(z);
   }

}

}

  1. [email protected]

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

  3. 5.1处,反了;“上一个操作符的优先级比操作符ch的优先级大,或栈是空的就入栈。”如代码所述,应为“上一个操作符的优先级比操作符ch的优先级小,或栈是空的就入栈。”