Edu 18 Colored balls -- 题解

目录

Colored Balls：

题目大意:

思路解析：

代码实现：

---

Colored Balls：

题目大意:

        

 

思路解析：

        我们对于一个数n，如果分组大小超过了 根号n，那么便不可能将n 分为多个组，并且组间差距最大为1.

        那么我们只需要找到数组a中最小的n，枚举 1-sqrtn，看其他数是否能满足这样的分组要求。在所有可满足的分组要求中找到最大的分组条件，这样就可以使得分组后的集合数尽量少。

        

代码实现：

import java.beans.IntrospectionException;
import java.io.*;
import java.math.BigInteger;
import java.util.*;

public class Main {
   static int n = 0;
   static int[] a;
   static int ans = Integer.MAX_VALUE;


    public static void main(String[] args) throws IOException {
        n = f.nextInt();
        int min = Integer.MAX_VALUE;
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = f.nextInt();
            min = Math.min(a[i], min);
        }
        int r = 0;
        int L, R;
        ArrayList<Integer> list = new ArrayList<>();
        for (int l = 1; l <= min; l = r + 1) {
            r = (min / ( min / l));
            int y = min / l;
            L = Math.max(l, (min + y - 1) / y - 1);
            R = r;
            if (L <= R && min % R <= min / R){
                list.add(L);
                list.add(R);
            }
        }
        int mx = 0;
        for (Integer b : list) {
            int flag = 1;
            for (int i = 0; i < n; i++) {
                if (a[i] % b > a[i] / b){
                    flag = 0;
                    break;
                }
            }
            if (flag == 1) mx = Math.max(mx, b);
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            ans += (a[i] + mx) / (mx + 1);
        }
        w.println(ans);
        w.flush();
        w.close();

    }

    static PrintWriter w = new PrintWriter(new OutputStreamWriter(System.out));
    static Input f = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}