首页 > 专题系列 > Java解POJ > POJ 2215 Parliament [解题报告] Java
2013
11-10

POJ 2215 Parliament [解题报告] Java

Parliament

问题描述 :

The representatives have to spend a lot of time in the Parliament. That is why PSOS want to choose their seats to have the best ones. The special committee was formed to check all the seats and give a score to each of them. The more attractive the seat is, the higher is its score. The score involves the upholstering of chairs, the position of cameras that could take picture of sleeping representative, e.t.c. It was not easy, but finally, after many months, the committee put a score to each seat. Unfortunatelly, it is not possible to take all the best seats. There is also a Security Committee that decided the representatives must sit all together, in a rectangular shape. Moreover, the election is still not over and PSOS do not know how many seats they are going to get. The Party needs a program that will read the score of each seat and then it will be able to determine the total score of any rectangular area.

输入:

At the first line there is a positive integer N stating the number of assignments to follow. Each assignment begins with a line consisting of two integers R and S, separated by space. R is the number of rows in the Parliament, S is the number of seats in every row (all rows are of the same size). It is known that no Parliament can have more than 1000 rows, nor more than 1000 seats in a row. Then R lines follow. Each of them describes one row of the Parliament, in sequence starting with the first one. Each line contains exactly S numbers separated by spaces. These numbers are score values of each seat in the given row, in sequence starting with the first one. The total score of all seats in the Parliament will always fit into the standard int or integer type.

Then the line containing the single integer number D follows. It is the number of queries. Then D lines follow, each specifying a single query. The query consists of four coordinates separated by spaces, R1, S1, R2, S2 (in that order), 1 <= R1 <= R2 <= R <= 1000, 1 <= S1 <= S2 <= S <= 1000. The coordinates designate that representatives are sitting at the seats forming a rectangle. The seats are in rows from R1 to R2 (including them) and in each of these row the seats from S1 to S2 (including them) are occupied.

输出:

Output a single line for each query. The line must contain the sentence “Absolutni hodnota pohodlnosti je X bodu.” (The total score is X points). Fill the total score instead of X. The total score is a sum of score values of each seat occupied by PSOS Party. Print one empty line after each assignment (including the last one).

样例输入:

2
10 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
5
1 1 1 1
2 2 2 2
1 1 10 10
9 9 10 10
2 2 9 9
1 1
1
1
1 1 1 1

样例输出:

Absolutni hodnota pohodlnosti je 1 bodu.
Absolutni hodnota pohodlnosti je 2 bodu.
Absolutni hodnota pohodlnosti je 550 bodu.
Absolutni hodnota pohodlnosti je 38 bodu.
Absolutni hodnota pohodlnosti je 352 bodu.

Absolutni hodnota pohodlnosti je 1 bodu.

解题代码:

//* @author:
import java.io.*;
import java.util.*;
public class Main { 
   static int SZ=1005;
   public static void main(String[] args) throws Exception {
    	int r,c,q;
    	int sum;
    	int i,j,x1,y1,x2,y2; 
   	int[][] area=new int[SZ][SZ]; 
   	for(i=0;i< SZ;++i) area[i][0]=0; 
   	Scanner cin=new Scanner(System.in); 
    	int T=cin.nextInt(); 
   	while(--T>=0) {
         r=cin.nextInt(); 
   	  c=cin.nextInt(); 
   	  for(i=0;i< r;++i)
    	   for(j=1;j<=c;++j){  
  		area[i][j]=cin.nextInt(); 
   		area[i][j]+=area[i][j-1];
   	   } 
   	   q=cin.nextInt();
   	   while(--q>=0)
    	   { 
   		x1=cin.nextInt(); 
   		y1=cin.nextInt(); 
   		x2=cin.nextInt(); 
   		y2=cin.nextInt(); 
   		sum=0; 
   		for(i=x1-1;i< x2;++i) 
   			sum+=area[i][y2]-area[i][y1-1]; 
              System.out.println("Absolutni hodnota pohodlnosti je "+sum+" bodu.");
    	    }  
  	    System.out.println("");
    	}  
 }  
}

  1. 第二种想法,我想来好久,为啥需要一个newhead,发现是把最后一个节点一直返回到嘴上面这层函数。厉害,这道题之前没样子想过。

  2. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  3. int half(int *array,int len,int key)
    {
    int l=0,r=len;
    while(l<r)
    {
    int m=(l+r)>>1;
    if(key>array )l=m+1;
    else if(key<array )r=m;
    else return m;
    }
    return -1;
    }
    这种就能避免一些Bug
    l,m,r
    左边是l,m;右边就是m+1,r;

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