首页 > 专题系列 > Java解POJ > POJ 1247 Magnificent Meatballs [解题报告] Java
2013
11-09

POJ 1247 Magnificent Meatballs [解题报告] Java

Magnificent Meatballs

问题描述 :

Sam and Ella run a catering service. They like to put on a show when serving meatballs to guests seated at round tables. They march out of the kitchen with pots of meatballs and start serving adjacent guests. Ella goes counterclockwise and Sam goes clockwise, until they both plop down their last meatball, at the same time, again at adjacent guests. This impressive routine can only be accomplished if they can divide the table into two sections, each having the same number of meatballs. You are to write a program to assist them.

At these catering events, each table seats 2 <= N <= 30 guests. Each guest orders at least one and at most nine meatballs. Each place at the table is numbered from 1 to N, with the host at position 1 and the host's spouse at position N. Sam always serves the host first then proceeds to serve guests in increasing order. Ella serves the spouse first, then serves guests in decreasing order. The figures illustrate the first two example input cases.

输入:

Input consists of one or more test cases. Each test case contains the number of guests N followed by meatballs ordered by each guest, from guest 1 to guest N. The end of the input is a line with a single zero.

输出:

For each table, output a single line with the ending positions for Sam and Ella, or the sentence indicating an equal partitioning isn’t possible. Use the exact formatting shown below.

样例输入:

5 9 4 2 8 3
5 3 9 4 2 8
6 1 2 1 2 1 2
6 1 2 1 2 1 1
0

样例输出:

Sam stops at position 2 and Ella stops at position 3.
No equal partitioning.
No equal partitioning.
Sam stops at position 3 and Ella stops at position 4.

解题代码:

//* @author: [email protected]
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  while(true)
  {
   int a=in.nextInt();
    if(a==0)break;
    int[] arr=new int[a];
    int t=0;
    for(int i=0;i< a;i++)
    {
	arr[i]=in.nextInt();
	t+=arr[i];
     }
    if(t%2==1)System.out.println("No equal partitioning.");	
    else
    {
	t=t/2;
	for(int i=0;i< a;i++)
	{
	  t-=arr[i];
	  if(t==0){
	   System.out.println("Sam stops at position "+(i+1)+" and Ella stops at position "+(i+2)+".");
		break;
	   }
	  else if(t< 0)
	  {
	   System.out.println("No equal partitioning.");
		break;
	   }
	}
     }
    }
  }
}

  1. 换句话说,A[k/2-1]不可能大于两数组合并之后的第k小值,所以我们可以将其抛弃。
    应该是,不可能小于合并后的第K小值吧

  2. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法