华为机试堆积木

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
package common;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Scanner;

public class HWTest2 {
    public static List<List<String>> combiner(List<String> elements, int num, List<List<String>> result) {
        // 当num为1时，即返回结果集
        if (num == 1) {
            return result;
        }
        // result的长度是变化的，故把原始值赋给变量leng
        int leng = result.size();
        // 循环遍历，将 elements每两个元素放到一起，作为result中的一个元素
        for (int i = 0; i < leng; i++) {
            for (int j = 0; j < elements.size(); j++) {
                if (!result.get(i).contains(elements.get(j))) {
                    List<String> list1 = new ArrayList<String>();
                    for (int j2 = 0; j2 < result.get(i).size(); j2++) {
                        list1.add(result.get(i).get(j2));
                    }
                    list1.add(elements.get(j));
                    Collections.sort(list1);
                    result.add(list1);
                }
            }
        } // 将result中的循环遍历前的数据删除
        for (int i = 0; i < leng; i++) {
            result.remove(0);
        }
        // 对result进行去重
        Iterator<List<String>> it = result.iterator();
        List<List<String>> listTemp = new ArrayList<List<String>>();
        while (it.hasNext()) {
            List<String> a = it.next();
            if (listTemp.contains(a)) {
                it.remove();
            } else {
                listTemp.add(a);
            }
        }
        // 递归计算，根据num的值来确定递归次数
        combiner(elements, num - 1, result);
        return result;
    }

    // elements为要操作的数据集合，即长度为M的容器，num为每次取的元素个数
    public static List<List<String>> findsort(List<String> elements, int num) {
        List<List<String>> result = new ArrayList<List<String>>();
        // 将elements中的数据取出来，存到新的list中，为后续计算做准备
        for (int i = 0; i < elements.size(); i++) {
            List<String> list = new ArrayList<String>();
            list.add(elements.get(i));
            result.add(list);
        }
        return combiner(elements, num, result);
    }

    // 验证
    public static void main(String args[]) {
        Scanner in = new Scanner(System.in);

        List<String> ls = Arrays.asList(in.nextLine().split(" "));

        ls.sort(Comparator.reverseOrder());
        // System.out.println(ls);
        int num = 0;
        for (String x : ls) {
            num = num + Integer.valueOf(x);
        }

        List<Integer> cs = new ArrayList<>();
        int max = ls.size();
        boolean flag = false;
        for (int i = max; i > 1; i--) {
            if (num % i != 0) {
                continue;
            }
            int avt = num / i;
            if (check(i, avt, ls)) {
                System.out.println(i);
                flag = true;
                break;
            }
        }
        if (!flag) {
            System.out.println(-1);
        }
    }

    private static boolean check(int max, int avt, List<String> data) {
        for (String d : data) {
            if (avt < Integer.valueOf(d)) {
                return false;
            }
        }
        List<String> ls = new ArrayList<>(data);
        Map<Integer, Integer> my = new HashMap();
        for (int i = 0; i < ls.size(); i++) {
            my.put(i, Integer.valueOf(ls.get(i)));
        }
        int len = ls.size();
        F1: for (int i = 1; i < len; i++) {
            ls.clear();
            for (int k : my.keySet()) {
                if (my.get(k) > 0) {
                    ls.add(String.valueOf(my.get(k)));
                }
            }
            // System.out.println(ls);
            List<List<String>> listSort = new ArrayList<>();
            if (ls.size() > i) {
                listSort = findsort(ls, i);
            } else {
                listSort.add(ls);
            }

            List<List<String>> list = new ArrayList<>();

            for (List<String> arr : listSort) {
                int t = 0;
                for (String s : arr) {
                    t = t + Integer.valueOf(s);
                }
                if (t == avt) {
                    list.add(arr);
                }
            }
            if (list.isEmpty()) {
                break;
            }
            F2: for (List<String> arr : list) {
                Map<Integer, Integer> tm = new HashMap<>();
                for (int k : my.keySet()) {
                    tm.put(k, my.get(k));
                }
                F3: for (String s : arr) {
                    if (!tm.containsValue(Integer.valueOf(s))) {
                        continue F2;
                    } else {
                        for (int k : tm.keySet()) {
                            if (tm.get(k) == Integer.valueOf(s)) {
                                tm.put(k, 0);
                                continue F3;
                            }
                        }
                    }
                }
                F4: for (String s : arr) {
                    F5: for (int k : my.keySet()) {
                        if (my.get(k) == Integer.valueOf(s)) {
                            my.put(k, 0);
                            continue F4;
                        }
                    }
                }
            }
        }
        for (int k : my.keySet()) {
            if (my.get(k) > 0) {
                return false;
            }
        }
        return true;
    }
}

Copyright ©2010-2022 比特日记 All Rights Reserved.

浙ICP备11005866号-12