首页 > 专题系列 > Java解POJ > POJ 1928 The Peanuts [解题报告] Java
2013
11-10

POJ 1928 The Peanuts [解题报告] Java

The Peanuts

问题描述 :

Mr. Robinson and his pet monkey Dodo love peanuts very much. One day while they were having a walk on a country road, Dodo found a sign by the road, pasted with a small piece of paper, saying “Free Peanuts Here! ” You can imagine how happy Mr. Robinson and Dodo were.

There was a peanut field on one side of the road. The peanuts were planted on the intersecting points of a grid as shown in Figure-1. At each point, there are either zero or more peanuts. For example, in Figure-2, only four points have more than zero peanuts, and the numbers are 15, 13, 9 and 7 respectively. One could only walk from an intersection point to one of the four adjacent points, taking one unit of time. It also takes one unit of time to do one of the following: to walk from the road to the field, to walk from the field to the road, or pick peanuts on a point.



According to Mr. Robinson’s requirement, Dodo should go to the plant with the most peanuts first. After picking them, he should then go to the next plant with the most peanuts, and so on. Mr. Robinson was not so patient as to wait for Dodo to pick all the peanuts and he asked Dodo to return to the road in a certain period of time. For example, Dodo could pick 37 peanuts within 21 units of time in the situation given in Figure-2.

Your task is, given the distribution of the peanuts and a certain period of time, tell how many peanuts Dodo could pick. You can assume that each point contains a different amount of peanuts, except 0, which may appear more than once.

输入:

The first line of input contains the test case number T (1 <= T <= 20). For each test case, the first line contains three integers, M, N and K (1 <= M, N <= 50, 0 <= K <= 20000). Each of the following M lines contain N integers. None of the integers will exceed 3000. (M * N) describes the peanut field. The j-th integer X in the i-th line means there are X peanuts on the point (i, j). K means Dodo must return to the road in K units of time.

输出:

For each test case, print one line containing the amount of peanuts Dodo can pick.

样例输入:

2
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0

样例输出:

37
28

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.Arrays;
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());
	while((a--)!=0)
	{
         String[] ss=in.readLine().split(" ");
	  int cow=Integer.parseInt(ss[0]);
	  int cul=Integer.parseInt(ss[1]);
	  int sum=Integer.parseInt(ss[2])-2;
	  my[] p=new my[cow*cul+3];
	  int l=1;
	  for(int i=0;i< cow;i++)
	  {
		ss=in.readLine().split(" ");
		for(int j=0;j< cul;j++)
		{
			int y=Integer.parseInt(ss[j]);
			if(y!=0)
			{
			  p[l]=new my();
			  p[l].x=i;
			  p[l].y=j;
			  p[l].n=y;
			  l++;
			}
		}
	    }
	   Arrays.sort(p,1,l);
	   p[0]=new my();
	   p[0].x=0;
	   p[0].y=p[1].y;
	   p[0].n=0;
	   int total=0;
	   for(int i=1;i< l;i++)
	   {
		int dis=Math.abs(p[i].x-p[i-1].x)+Math.abs(p[i].y-p[i-1].y);
		if(sum>=dis+1+p[i].x)
		{
			sum=sum-dis-1;
			total+=p[i].n;
		}
		else break;
	    }
	   System.out.println(total);
	}
   }
}

class my implements Comparable< my>
{
	int x;
	int y;
	int n;
	@Override
	public int compareTo(my arg0) {
		return arg0.n-n;
	}
}

  1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同,其树的前、中、后序遍历是相同的,但在此处不能使用中序遍历,因为,中序遍历的结果就是排序的结果。经在九度测试,运行时间90ms,比楼主的要快。

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  3. Hello Web Admin, I noticed that your On-Page SEO is is missing a few factors, for one you do not use all three H tags in your post, also I notice that you are not using bold or italics properly in your SEO optimization. On-Page SEO means more now than ever since the new Google update: Panda. No longer are backlinks and simply pinging or sending out a RSS feed the key to getting Google PageRank or Alexa Rankings, You now NEED On-Page SEO. So what is good On-Page SEO?First your keyword must appear in the title.Then it must appear in the URL.You have to optimize your keyword and make sure that it has a nice keyword density of 3-5% in your article with relevant LSI (Latent Semantic Indexing). Then you should spread all H1,H2,H3 tags in your article.Your Keyword should appear in your first paragraph and in the last sentence of the page. You should have relevant usage of Bold and italics of your keyword.There should be one internal link to a page on your blog and you should have one image with an alt tag that has your keyword….wait there's even more Now what if i told you there was a simple WordPress plugin that does all the On-Page SEO, and automatically for you? That's right AUTOMATICALLY, just watch this 4minute video for more information at.