首页 > 专题系列 > Java解POJ > POJ 1455 Crazy tea party [解题报告] Java
2013
11-09

POJ 1455 Crazy tea party [解题报告] Java

Crazy tea party

问题描述 :

n participants of << crazy tea party >> sit around the table. Each minute one pair of neighbors can change their places. Find the minimum time (in minutes) required for all participants to sit in reverse order (so that left neighbors would become right, and right – left).

输入:

The first line is the amount of tests. Each next line contains one integer n (1 <= n <= 32767) - the amount of crazy tea participants.

输出:

For each number n of participants to crazy tea party print on the standard output, on a separate line, the minimum time required for all participants to sit in reverse order.

样例输入:

3
4
5
6

样例输出:

2
4
6

解题代码:

//* @author: [email protected]
import java.util.Scanner;
public class Main
{
  public static void main(String[] args)
  {
	Scanner in=new Scanner(System.in);
	int a=in.nextInt();
	while((a--)!=0)
	{
		int b=in.nextInt();
		int ans=0;
		int c=b/2;
		if(b%2==0) ans=c*(c-1);
		else ans=c*c;
		System.out.println(ans);
	}
  }
}

  1. a是根先忽略掉,递归子树。剩下前缀bejkcfghid和后缀jkebfghicd,分拆的原则的是每个子树前缀和后缀的节点个数是一样的,根节点出现在前缀的第一个,后缀的最后一个。根节点b出现后缀的第四个位置,则第一部分为四个节点,前缀bejk,后缀jkeb,剩下的c出现在后缀的倒数第2个,就划分为cfghi和 fghic,第3部分就为c、c