统计
  • 建站日期:2021-03-10
  • 文章总数:699 篇
  • 评论总数:733 条
  • 分类总数:10 个
  • 最后更新:12月4日
文章 精密算法

Java 蓝桥杯 国赛 第十一届 C组 试题J:答疑

程序员阿鑫
首页 精密算法 正文


Java蓝桥杯国赛第十一届C组试题J:答疑
-程序员阿鑫-带你一起秃头!
-第1
张图片

#J 答疑

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


问题描述

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

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

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


输入格式

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


输出格式

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


测试样例1

Input:
3
10000 10000 10000
20000 50000 20000
30000 20000 30000

Output:
280000

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

评测用例规模与约定

对于 30 3030% 的评测用例,1 ≤ n ≤ 20 1 ≤ n ≤ 201n20
对于 60 6060% 的评测用例,1 ≤ n ≤ 200 1 ≤ n ≤ 2001n200
对于所有评测用例,1 ≤ n ≤ 1000 1 ≤ n ≤ 10001n10001 ≤ s i ≤ 60000 1 ≤ s_{i} ≤ 600001si600001 ≤ a i ≤ 1000000 1 ≤ a_{i} ≤ 10000001ai1000000
e i ∈ { 10000 , 20000 , 30000 } e_{i} in {10000,20000,30000}ei{10000,20000,30000},即 e i e_{i}ei 一定是 10000 、 20000 、 30000 10000、20000、30000100002000030000 之一。


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:答疑》的全部内容,

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

版权说明
文章采用: 《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权。
版权声明:未标注转载均为本站原创,转载时请以链接形式注明文章出处。如有侵权、不妥之处,请联系站长删除。敬请谅解!

-- 展开阅读全文 --
这篇文章最后更新于2021-1-4,已超过 1 年没有更新,如果文章内容或图片资源失效,请留言反馈,我们会及时处理,谢谢!
C盘系统垃圾清理 真实有效 站长亲测!
« 上一篇
Java 蓝桥杯 国赛 第十一届 C组 试题I:画廊
下一篇 »
为了防止灌水评论,登录后即可评论!
注册登录

HI ! 请登录
注册会员,享受下载全站资源特权。
登陆 注册
上号,带你一起秃头!

IP地址

热门文章

1
抖音无限礼物模拟小工具分享
2
QQ假红包引流QQ群教程及代码
4
卡QQ永久大会员方法

最新文章

标签