首页 > 数据结构 > Hash表 > POJ 2549 Sumsets [解题报告] Java
2013
11-11

POJ 2549 Sumsets [解题报告] Java

Sumsets

问题描述 :

Given S, a set of integers, find the largest d such that a + b + c = d where a, b, c, and d are distinct elements of S.

输入:

Several S, each consisting of a line containing an integer 1 <= n <= 1000 indicating the number of elements in S, followed by the elements of S, one per line. Each element of S is a distinct integer between -536870912 and +536870911 inclusive. The last line of input contains 0.

输出:

For each S, a single line containing d, or a single line containing “no solution”.

样例输入:

5
2 
3 
5 
7 
12
5
2 
16 
64 
256 
1024
0

样例输出:

12
no solution

解题代码:

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;


/**
 * Accepted.
 * 
 * @author Administrator
 *
 */
public class Main {

    private static Set< Long> set = new HashSet< Long>();

    private static Map< Long, List< String>> map = new HashMap< Long, List< String>>();

    private static Set< Long> sumSet = new HashSet< Long>();

    /**
     * @param args
     */
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (true) {
            int n = cin.nextInt();

            if (n == 0) {
                break;
            }

            set.clear();
            sumSet.clear();

            map = new HashMap< Long, List< String>>();

            int[] a = new int[n];

            for (int i = 0; i < n; i++) {
                a[i] = cin.nextInt();

                set.add(new Long(a[i]));
            }

            Arrays.sort(a);

            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (a[i] != a[j]) {
                        long temp = a[i];
                        temp += a[j];
                        sumSet.add(temp);
                    }
                }
            }


            for (int i = n - 1; i >= 0; i--) {
                for (int j = i - 1; j >= 0; j--) {

                    if (a[i] == a[j]) {
                        continue;
                    }

                    long v = a[i];
                    v -= a[j];

                    if (!sumSet.contains(v)) {
                        // System.out.println("v=" + v);
                        continue;
                    }

                    List list = map.get(v);

                    if (list == null) {
                        list = new ArrayList();
                        list.add("" + a[i] + " " + a[j]);
                    } else {

                        list.add("" + a[i] + " " + a[j]);
                    }

                    map.put(v, list);
                }
            }
            int ans = 0;
            boolean find = false;

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (a[i] == a[j]) {
                        continue;
                    }

                    long sum = a[i];
                    sum += a[j];
                    List< String> list = map.get(sum);
                    // System.out.println("list=" + list);

                    if (list != null) {
                        for (String s : list) {

                            String[] ss = s.split("[ ]+");

                            int d = Integer.parseInt(ss[0]);
                            int c = Integer.parseInt(ss[1]);

                            if (d != a[i] && d != a[j] && c != a[i] && c != a[j]) {
                                find = true;
                                ans = Math.max(ans, d);
                            }
                        }
                    }
                }
            }

            if (find) {
                System.out.println(ans);
            } else {
                System.out.println("no solution");
            }
        }
    }
}

  1. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  2. 这道题目的核心一句话是:取还是不取。
    如果当前取,则index+1作为参数。如果当前不取,则任用index作为参数。