2020第十一届蓝桥杯国赛-H答疑

题面

【问题描述】

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

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

一位同学离开办公室后，紧接着下一位同学就可以进入办公室了。

答疑从 0 时刻开始。老师想合理的安排答疑的顺序，使得同学们在课程群 里面发消息的时刻之和最小。

【输入格式】

输入第一行包含一个整数 $n$，表示同学的数量。

接下来 $n$ 行，描述每位同学的时间。其中第 $i$ 行包含三个整数 $s_i$ , $a_i$ , $e_i$，意义如上所述。

【输出格式】

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

【样例输入】

3 
10000 10000 10000
20000 50000 20000
30000 20000 30000

【样例输出】

280000

【样例说明】

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

【评测用例规模与约定】

对于 30% 的评测用例，$1 ≤ n ≤ 20$。

对于 60% 的评测用例，$1 ≤ n ≤ 200$。

对于所有评测用例，$1 ≤ n ≤ 1000,\ 1 ≤ si ≤ 60000,\ 1 ≤ ai ≤ 1000000,\ e_i \in \{10000, 20000, 30000\}$，即 $e_i$ 一定是 10000、20000、30000 之一。

思路

AC思路：贪心。

证明：

对于两个相邻的同学 i 和 i + 1，假设前面同学答疑完毕已经消耗了 t 毫秒的时间。

第i个同学答疑成功发消息的时刻为 $t + s[i] + a[i]$， 答疑后离开办公室的时间为 $t + s[i] + a[i] + e[i]$。

而接下来的同学 i + 1​，答疑完成发消息的时刻为 $t + s[i] + a[i] + e[i] + s[i + 1] + a[i + 1]$，答疑完成离开办公室的时间为 $t + s[i] + a[i] + e[i] + s[i + 1] + a[i + 1] + e[i + 1]$。

则可以得知，这两位同学发消息的时间总和为

$t + 2\times s[i] + 2\times a[i] + e[i] + s[i+1]+a[i+1]$

都完成答疑后的时间为

$t + s[i] + a[i] + e[i] + s[i+1]+a[i+1]+e[i+1]$

考虑交换这两位同学的顺序。

则有第i+1个同学答疑成功发消息的时刻为 $t + s[i+1] + a[i+1]$， 答疑后离开办公室的时间为 $t + s[i+1] + a[i+1] + e[i+1]$。

而接下来的同学 i​，答疑完成发消息的时刻为 $t + s[i+1] + a[i+1] + e[i+1] + s[i] + a[i]$，答疑完成离开办公室的时间为 $t + s[i+1] + a[i+1] + e[i+1] + s[i] + a[i] + e[i]$。

则可以得知，这两位同学发消息的时间总和为

$t + s[i] + a[i] + e[i+1] + 2\times s[i+1]+2\times a[i+1]$

都完成答疑后的时间为

$t + s[i] + a[i] + e[i] + s[i+1]+a[i+1]+e[i+1]$

综上所述，交换两个相邻位置的同学，其完成答疑后的时间不会改变，但不同顺序进行答疑，前后相差

$sub = s[i]+a[i]+e[i]-(s[i+1]+a[i+1]+e[i+1])$

当 $sub > 0$ 则说明交换 i 同学和 i+1 同学交换后的发消息时间减少了，先安排 i+1 同学再 i 同学比较好。反之，则交换后发消息的时间增多了或者没有变化，则不交换按照原顺序即可。证毕。

显然，比较两个同学是否交换即观察其三个属性之和 $s+a+e$ 的大小关系。

代码

#include<iostream>
#include<algorithm>

using namespace std;
typedef long long LL;
const int N = 1005;
int n;

struct Stu {
    int s, a, e;

    bool operator<(Stu &b) {
        int s1 = s + a + e;
        int s2 = b.s + b.a + b.e;
        return s1 < s2;
    }
} stu[N];

//贪心
int main() {
    while (~scanf("%d", &n)) {
        LL res = 0, t = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d", &stu[i].s, &stu[i].a, &stu[i].e);
        }

        sort(stu, stu + n);
        for (int i = 0; i < n; i++) {
            res += t + stu[i].s + stu[i].a;
            t += stu[i].s + stu[i].a + stu[i].e;
        }

        printf("%lld\n", res);
    }

    return 0;
}