首页 > 专题系列 > Java解POJ > POJ 1552 Doubles [解题报告] Java
2013
11-09

POJ 1552 Doubles [解题报告] Java

Doubles

问题描述 :

As part of an arithmetic competency program, your students will be given randomly generated lists of from 2 to 15 unique positive integers and asked to determine how many items in each list are twice some other item in the same list. You will need a program to help you with the grading. This program should be able to scan the lists and output the correct answer for each one. For example, given the list

1 4 3 2 9 7 18 22



your program should answer 3, as 2 is twice 1, 4 is twice 2, and 18 is twice 9.

输入:

The input will consist of one or more lists of numbers. There will be one list of numbers per line. Each list will contain from 2 to 15 unique positive integers. No integer will be larger than 99. Each line will be terminated with the integer 0, which is not considered part of the list. A line with the single number -1 will mark the end of the file. The example input below shows 3 separate lists. Some lists may not contain any doubles.

输出:

The output will consist of one line per input list, containing a count of the items that are double some other item.

样例输入:

1 4 3 2 9 7 18 22 0
2 4 8 10 0
7 5 11 13 1 3 0
-1

样例输出:

3
2
0

解题代码:

import java.util.*;   
  
public class Main {   
  
    public static void main(String[] args) {   
        Scanner cin = new Scanner(System.in);   
           
        while(true)   
        {   
            String temp = cin.nextLine();   
            if(temp.equals("-1"))   
                break;   
            temp = temp.substring(0, temp.length()-1).trim();   
  
            int[] num = new int[15];   
            String[] str = temp.split(" ");   
            for(int i = 0; i < str.length; i++)   
                num[i] = Integer.valueOf(str[i]).intValue();   
           
            int result = 0;   
            for(int i = 0; i < str.length; i++)   
            {   
                for(int j = 0; j < str.length; j++)   
                    if(num[i] == num[j] * 2)   
                        result++;   
            }   
            System.out.println(result);   
        }   
  
    }   
  
}

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

  2. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }