#J 答疑

时间限制: 3.0s 内存限制: 512.0MB 本题总分：25 分

问题描述

有 $n$ 位同学同时找老师答疑。每位同学都预先估计了自己答疑的时间。
老师可以安排答疑的顺序，同学们要依次进入老师办公室答疑。
一位同学答疑的过程如下：

1. 首先进入办公室，编号为 $i$ 的同学需要 s i s_{i}si​ 毫秒的时间。
2. 然后同学问问题老师解答，编号为 $i$ 的同学需要 a i a_{i}ai​ 毫秒的时间。
3. 答疑完成后，同学很高兴，会在课程群里面发一条消息，需要的时间可以忽略。
4. 最后同学收拾东西离开办公室，需要 e i e_{i}ei​ 毫秒的时间。一般需要 $10$ 秒、$20$ 秒或 $30$ 秒，即 e i e_{i}ei​ 取值为 $10000$，$20000$ 或$30000$。

一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。
答疑从 $0$ 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群里面发消息的时刻之和最小。

输入格式

输入第一行包含一个整数 $n$，表示同学的数量。
接下来 $n$ 行，描述每位同学的时间。其中第 $i$ 行包含三个整数 s i s_{i}si​, a i a_{i}ai​, e i e_{i}ei​，意义如上所述。

输出格式

输出一个整数，表示同学们在课程群里面发消息的时刻之和最小是多少。

测试样例₁

Input：
3
10000 10000 10000
20000 50000 20000
30000 20000 30000

Output：
280000

Explanation：
按照 1, 3, 2 的顺序答疑，发消息的时间分别是 20000, 80000, 180000。

评测用例规模与约定

对于 $30$% 的评测用例，$1\le n\le 20$。
对于 $60$% 的评测用例，$1\le n\le 200$。
对于所有评测用例，$1\le n\le 1000$，1 ≤ s i ≤ 60000 1 ≤ s_{i} ≤ 600001≤si​≤60000，1 ≤ a i ≤ 1000000 1 ≤ a_{i} ≤ 10000001≤ai​≤1000000，
e i ∈ { 10000 , 20000 , 30000 } e_{i} in {10000,20000,30000}ei​∈{10000,20000,30000}，即 e i e_{i}ei​ 一定是 $10000、20000、30000$ 之一。

code：

import java.io.*;
import java.util.Arrays;

public class Main {

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        int n = (int)in.nval;
        Per[] arr = new Per[n];
        for (int i = 0, o, e; i < n; i++) {
            in.nextToken();
            o = (int)in.nval;
            in.nextToken();
            o += in.nval;
            in.nextToken();
            e = (int)in.nval;
            arr[i] = new Per(o, e, o + e);
        }
        Arrays.sort(arr);
        long offset = 0, res = 0;
        for (int i = 0; i < n; i++) {
            res += offset += arr[i].offset;
            offset += arr[i].e;
        }
        System.out.println(res);
    }

    static class Per implements Comparable<Per> {

        int offset, s, e;

        Per(int offset, int e, int s) {
            this.offset = offset;
            this.e = e;
            this.s = s;
        }

        public int compareTo(Per per) {
            if (this.s == per.s) return per.offset - this.offset;
            return this.s - per.s;
        }
    }
}

你没有看错，n ≤ 1000 的贪心排序，出现在了蓝桥国赛上，还是商业化程度高了

写了个校验程序

import java.io.*;
import java.util.Arrays;
import java.util.Random;

public class Test {

    public static void main(String[] args) throws IOException {
        int n, e[] = { 10000, 20000, 30000 }, buff[][] = new int[10000][3];
        ByteArrayOutputStream data = new ByteArrayOutputStream();
        Random random = new Random();
        int cnt = 1;
        while (true) {
            data.reset();
            n = random.nextInt(12);
            data.write(String.valueOf(n).getBytes());
            data.write('n');
            for (int i = 0; i < n; i++) {
                data.write(String.valueOf(buff[i][0] = random.nextInt(1000000) + 1).getBytes());
                data.write(' ');
                data.write(String.valueOf(buff[i][1] = random.nextInt(60000) + 1).getBytes());
                data.write(' ');
                data.write(String.valueOf(buff[i][2] = e[random.nextInt(3)]).getBytes());
                data.write('n');
            }
            System.out.printf("第 %d 次测试结果: %sn", cnt++, violent(buff, n, 0) == finale(new ByteArrayInputStream(data.toByteArray())));
        }
    }

    static int violent(int[][] data, int n, int cur) {
        if (n == cur) {
            int res = 0, offset = 0;
            for (int i = 0; i < n; i++) {
                res += offset += data[i][0] + data[i][1];
                offset += data[i][2];
            }
            return res;
        } else {
            int res = 0x3F3F3F3F;
            for (int i = cur; i < n; i++) {
                swap(data, i, cur);
                res = min(res, violent(data, n, cur + 1));
                swap(data, i, cur);
            }
            return res;
        }
    }

    static int min(int a, int b) { return a < b ? a : b; }

    static void swap(int[][] a, int i1, int i2) {
        int[] tmp = a[i1];
        a[i1] = a[i2];
        a[i2] = tmp;
    }

    static int finale(InputStream data) throws IOException {
        class Per implements Comparable<Per> {

            int offset, s, e;

            Per(int offset, int e, int s) {
                this.offset = offset;
                this.e = e;
                this.s = s;
            }

            public int compareTo(Per per) {
                if (this.s == per.s) return per.offset - this.offset;
                return this.s - per.s;
            }
        }
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(data)));
        in.nextToken();
        int n = (int)in.nval;
        Per[] arr = new Per[n];
        for (int i = 0, o, e; i < n; i++) {
            in.nextToken();
            o = (int)in.nval;
            in.nextToken();
            o += in.nval;
            in.nextToken();
            e = (int)in.nval;
            arr[i] = new Per(o, e, o + e);
        }
        Arrays.sort(arr);
        int offset = 0, res = 0;
        for (int i = 0; i < n; i++) {
            res += offset += arr[i].offset;
            offset += arr[i].e;
        }
        return res;
    }
}

以上是《Java 蓝桥杯 国赛 第十一届 C组 试题J：答疑》的全部内容，

感谢您对程序员阿鑫博客的支持！