首页 > 专题系列 > Java解POJ > POJ 1011 Sticks [解题报告] Java
2013
11-08

POJ 1011 Sticks [解题报告] Java

Sticks

问题描述 :

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

输入:

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

输出:

The output should contains the smallest possible length of original sticks, one per line.

样例输入:

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

样例输出:

6
5

解题代码:

import java.io.BufferedReader;
 import java.io.InputStreamReader;
 import java.util.Arrays;
 import java.util.StringTokenizer;

 public class Main {

     static boolean[] used;
     static int len;
     static int[] s;
     static int sum;
     static int max;
     static int parts;

     public static void main(String[] args) throws Exception {
         BufferedReader read = new BufferedReader(new InputStreamReader(
                 System.in));
         while ((len = Integer.parseInt(read.readLine())) != 0) {
             s = new int[len];
             StringTokenizer take = new StringTokenizer(read.readLine());
             int index = 0;
             sum = 0;
             used = new boolean[len];
             while (take.hasMoreTokens()) {
                 s[index] = Integer.parseInt(take.nextToken());
                 sum += s[index++];
             }
             Arrays.sort(s);
             max = s[len - 1];
             for (; max <= sum; max++) {
                 if (sum % max == 0) {
                     parts = sum / max;
                     if (search(0, len - 1, 0)) {
                         System.out.println(max);
                         break;
                     }
                 }
             }
         }
     }

     public static boolean search(int res, int next, int cpl) {
         if (res == max) {
             res = 0;
             next = len - 2;
             cpl++;
         }
         if (cpl == parts) {
             return true;
         }
         while (next >= 0) {
             if (used[next] == false) {
                 if (res + s[next] <= max) {
                     used[next] = true;
                     if (search(res + s[next], next - 1, cpl)) {
                         return true;
                     }
                     used[next] = false;
                     if (res == 0) {
                         break;
                     }
                     if (res + s[next] == max) {
                         break;
                     }
                 }
                 int i = next - 1;
                 while (i >= 0 && s[i] == s[next]) {
                     i--;
                 }
                 next = i;
                 int l_s = 0;
                 for (int j = next; j >= 0; j--) {
                     if (!used[j]) {
                         l_s += s[j];
                     }
                 }
                 if (l_s < max - res) {
                     break;
                 }
                 continue;
             }
             next--;
         }
         return false;
     } 
}

  1. #include <stdio.h>
    int main()
    {
    int n,p,t[100]={1};
    for(int i=1;i<100;i++)
    t =i;
    while(scanf("%d",&n)&&n!=0){
    if(n==1)
    printf("Printing order for 1 pages:nSheet 1, front: Blank, 1n");
    else {
    if(n%4) p=n/4+1;
    else p=n/4;
    int q=4*p;
    printf("Printing order for %d pages:n",n);
    for(int i=0;i<p;i++){
    printf("Sheet %d, front: ",i+1);
    if(q>n) {printf("Blank, %dn",t[2*i+1]);}
    else {printf("%d, %dn",q,t[2*i+1]);}
    q–;//打印表前
    printf("Sheet %d, back : ",i+1);
    if(q>n) {printf("%d, Blankn",t[2*i+2]);}
    else {printf("%d, %dn",t[2*i+2],q);}
    q–;//打印表后
    }
    }
    }
    return 0;
    }

  2. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  3. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。