P3745 [六省联考2017]期末考试

    • 456通过
    • 1.5K提交
  • 题目提供者 SakuraDance
  • 评测方式 云端评测
  • 标签 前缀和 数论,数学 枚举,暴力 贪心 各省省选 2017 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    有 $n$ 位同学,每位同学都参加了全部的 $m$ 门课程的期末考试,都在焦急的等待成绩的公布。

    第 $i$ 位同学希望在第 $t_i$ 天或之前得知所有课程的成绩。如果在第 $t_i$ 天,有至少一门课程的成绩没有公布,他就会等待最后公布成绩的课程公布成绩,每等待一天就会产生 $C$ 不愉快度。

    对于第 $i$ 门课程,按照原本的计划,会在第 $b_i$ 天公布成绩。

    有如下两种操作可以调整公布成绩的时间:

    1. 将负责课程 $X$ 的部分老师调整到课程 $Y$,调整之后公布课程 $X$ 成绩的时间推迟一天,公布课程 $Y$ 成绩的时间提前一天;每次操作产生 $A$ 不愉快度。
    2. 增加一部分老师负责学科 $Z$,这将导致学科 $Z$ 的出成绩时间提前一天;每次操作产生 $B$ 不愉快度。

    上面两种操作中的参数 $X, Y, Z$ 均可任意指定,每种操作均可以执行多次,每次执行时都可以重新指定参数。

    现在希望你通过合理的操作,使得最后总的不愉快度之和最小,输出最小的不愉快度之和即可。

    输入输出格式

    输入格式:

    第一行三个非负整数 $A, B, C$,描述三种不愉快度,详见【题目描述】;
    第二行两个正整数 $n, m$,分别表示学生的数量和课程的数量;
    第三行 $n$ 个正整数 $t_i$,表示每个学生希望的公布成绩的时间;
    第四行 $m$ 个正整数 $b_i$,表示按照原本的计划,每门课程公布成绩的时间。

    输出格式:

    输出一行一个整数,表示最小的不愉快度之和。

    输入输出样例

    输入样例#1: 复制
    100 100 2
    4 5
    5 1 2 3
    1 1 2 3 3
    输出样例#1: 复制
    6
    输入样例#2: 复制
    3 5 4
    5 6
    1 1 4 7 8
    2 3 3 1 8 2
    输出样例#2: 复制
    33

    说明

    【样例 1 说明】

    由于调整操作产生的不愉快度太大,所以在本例中最好的方案是不进行调整; 全部

    5 的门课程中,最慢的在第 3 天出成绩;

    同学 1 希望在第 5 天或之前出成绩,所以不会产生不愉快度;

    同学 2 希望在第 1 天或之前出成绩,产生的不愉快度为 (3 − 1) ∗ 2 = 4;

    同学 3 希望在第 2 天或之前出成绩,产生的不愉快度为 (3 − 2) ∗ 2 = 2;

    同学 4 希望在第 3 天或之前出成绩,所以不会产生不愉快度;

    不愉快度之和为 4 + 2 = 6 。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。