首页 > 专题系列 > Java解POJ > POJ 2967 Triangles [解题报告] Java
2013
11-12

POJ 2967 Triangles [解题报告] Java

Triangles

问题描述 :

triDesign company produces different logical games and puzzles for children. One of the games called triSuper is basically a set of sticks. The length of a stick is measured in millimeters and some of sticks in a set may be of the same length.

Authors of the game think for some reason that a child being given a triSuper game set uses the sticks to construct triangles. Doing so, the child will eventually realize that it is not always possible to construct a triangle from any three sticks. This is the educational value of the game – to study “the inequality of a triangle”.

A particular feature of the game is that each game set is unique. Furthermore, each game set is tested after production. The game set is rejected if it breaks any of the following rules.

  1. None three sticks from the set can be used to construct a triangle.
  2. Any three sticks from the set can be used to construct a triangle.

As far as a game set may contain a lot of sticks, it is necessary to develop special program to help testing game sets. This is what you need to do.

输入:

The input describes one game set. The first line of the input contains an integer number N (1 ≤ N ≤ 1 000 000). The second line contains N integer numbers A1, A2, …, AN, separated by spaces (1 ≤ Ai ≤ 2 000 000 000). Ai is the length of the stick number i in the set. Sticks in the set a so thin, that you can disregard their thickness.

输出:

The output has to contain a single line. If a game set is rejected than the line is “The set is rejected.”. Otherwise, the line is “The set is accepted.”

样例输入:

sample input #1
3
1 2 3

sample input #2
4
4 4 4 4

sample input #3
4
1 2 3 4

样例输出:

sample output #1
The set is rejected.

sample output #2
The set is rejected.

sample output #3
The set is accepted.

解题代码:

//* @author: [email protected]
import java.util.*;
import java.io.*;
public class Main
{
 public static void main(String[] args) throws IOException
 {
  InputStreamReader is=new InputStreamReader(System.in);
  BufferedReader in=new BufferedReader(is);
  int a=Integer.parseInt(in.readLine());
  int[] arr=new int[a];
  int u,total;
  for(int i=0;i< a;i++)
  {
	total=0;
	while(true)
	{
         u=in.read();
	  if(u>'9'||u< '0')break;
		total*=10;
		total+=u-'0';
	}
	arr[i]=total;
    }
    if(a< 4)
	System.out.println("The set is rejected.");
    else
    {
	Arrays.sort(arr);
	if(arr[a-1]-arr[0]< arr[1])
		System.out.println("The set is rejected.");
	else{
	  boolean bb=false;
	  for(int i=a-1;i>=2;i--)
	  {
	    if(arr[i]-arr[i-2]< arr[i-1])
	    {
		System.out.println("The set is accepted.");
		bb=true;
		break;
	    }
	   }
	   if(!bb) System.out.println("The set is rejected.");
	}
     }
  }
}

  1. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?