关于我在数学课上讲贪心这件事

· · 学习·文化课

起因

昨天在数学课上做到了这样一道题：

联欢会有ABCD四个节目需要彩排，所有演员到场后彩排开始，一个节目彩排完毕，下一个节目彩排立即开始。每个节目演员人数和彩排时长如下：

节目-演员人数-彩排时长
A-10-30
B-2-10
C-10-20
D-1-10

每位演员只演一个节目。一位演员的候场时间为从第一个彩排的节目彩排开始到这位演员参演的节目彩排开始的时间（不考虑换场等其他因素）。

若使这些演员的候场时间之和最小，则节目应按怎样的先后顺序彩排？

只考虑这样一个问题未免太没意思了，那么我们不妨考虑将问题扩展到这样——

问题

联欢会有1,2,3…n这n个节目需要彩排，第i个节目的演员人数为a_i，彩排时间为t_i，所有演员到场后彩排开始，一个节目彩排完毕，下一个节目彩排立即开始。

每位演员只演一个节目。一位演员的候场时间为从第一个彩排的节目彩排开始到这位演员参演的节目彩排开始的时间（不考虑换场等其他因素）。

要使这些演员的候场时间之和最小，输出节目彩排的先后顺序

解法

最开始拿到这个题的时候只能想出来O(n!)的DFS解法，但这样一道题肯定是可以有更好的解法的，于是经历了一个中午的时间想出了O(n log n)的贪心解法——

首先，1,2,3…n这种排列方式的候场时间之和为

a_2t_1+a_3(t_1+t_2)+…+a_n(t_1+t_2+…+t_{n-1})

也就是

\sum_{i=2}^{n}(a_i\sum_{j=1}^{i-1}t_i)

我们不妨考虑其中第i个和第i+1个这两个相邻的节目:
当我们调换这两个节目的顺序时，其他节目的演员候场时间显然不变，而这两个节目的演员等待第1个到第i-1个节目的时间显然也不变，只有第i+1个节目演员等待第i个节目的时间变为了第i个节目的演员等待第i+1个节目的时间，也就是从a_{i+1}t_i变为了a_it_{i+1}

我们不妨令调换之前的方式更优，则有：

a_it_{i+1} \ge a_{i+1}t_i

两边同除t_it_{i+1}，得

\frac{a_i}{t_i} \ge \frac{a_{i+1}}{t_{i+1}}

因此，我们只需让序列中的\frac{a}{t}保持单调不增就可以了

所以，这个问题的解法就是：
对于每一个节目，都求出其\frac{a}{t}的值，再按这个值从大到小排序，即为所求

时间复杂度为排序的O(nlogn)

体感难度在橙到黄左右

标程

#include<bits/stdc++.h>
using namespace std;
const int M = 1001000;
int n;
struct program{
    int a , t , no;
    double ans/* a/t的值 */;
}pg[M];
bool cmp(program A , program B){
    return A.ans >= B.ans;
}
int main(){
    ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0);
    cin>>n;
    for(int i = 1; i <= n; ++i) cin>>pg[i].a;
    for(int i = 1; i <= n; ++i) cin>>pg[i].t;
    for(int i = 1; i <= n; ++i){
        pg[i].no = i;
        pg[i].ans = 1.0 * pg[i].a / pg[i].t;
    }
    sort(pg + 1 , pg + 1 + n , cmp);
    for(int i = 1; i <= n; ++i) cout<<pg[i].no<<endl;
    return 0;
}

？？？

当时我在数学课上真就这么讲的……qwq
同学们大概是听懂了……吧……

哦对了，这个题要选出最佳方案，所以是Choose Choose Best