算法笔试之二分与贪心

回国一直笔试不断，面试一直挂，稍有难度的场次这是第一次AK，算是复健有一定成效。也和题目不那么难有关系。

首先是一道序列操作，给包装了一堆，下面是题目大意：

定义序列的加法运算，是一个序列$A$和一个常数$x$的运算，结果得到一个序列，元素值为原序列对应位置元素加上该常数。记作$A+x$。

定义序列的乘法运算，注意不满足交换律，是一个序列$A$和另一个序列$B$的运算，结果得到一个序列，就是$A$的所有元素后面跟上$B$的所有元素。记作$AB$。

题目定义一个序列$A$上的操作，操作后变为$(A+1)A$

题目给定一个初始序列，仅有一个元素$x(10^5)$，问进行$k(60)$次操作后，序列中第$m(2^{60})$个元素是什么。

这个手动模拟一下就知道，首先这个序列最后都只在$x$的基础上加一个常数，所以先按$x=0$算到最后加上$x$即可。

然后注意到每次序列长度都是翻倍的，都是重复原序列的模式，那么很容易猜测和倍增有关。考试时间紧张，我直接从结果入手，看看最后的结果和他的下标二进制之间的关系。例如操作3次后，序列长度为8：

很容易观察出，结果和下标二进制中1的个数有关，就是操作次数-下标二进制中1的个数。至于为什么这样也很容易证明，但出于时间考虑不用管那么多，直接写代码实现即可，复杂度$O(\log m)=O(k)$，AC。

然后是一道安排时间的问题，题目大意如下：

某个银行只有一名业务员，只能同时处理一个人的业务。

由于业务员人数有限，所以除了正在办理业务的人以外，其他所有人都需要等待前一个人的业务完成。

共有 $n(10^5)$ 个人，每个人都有一个需要办理的业务。 对于第 $i$ 个人：

他的业务基础办理时间为 $a[i](10^5)$ 分钟；

若他每等待 1 分钟，其最终办理时间会额外增加 $b[i](10^5)$ 分钟。

因此如果第 $i$ 个人的等待时间为 $w$，则他的实际办理时间为：

$p[i] = a[i] + b[i] \times w$

每个人的总耗时（等待时间 + 办理时间）为：

$t[i] = w + p[i]$

最小化 $\Sigma t[i]$ 并输出。答案对 $10^9 + 9$ 取模。

乍一看，这不是排队接水吗。看得我很难绷，想起初中训练的时候教练没讲清楚就抓人上去写排队接水，我们几个就去百度，结果百度全是这种：

我就在下面开始偷笑，同伴还严肃提醒我这样态度不对且会引起老师注意。

回到题目上，乍一看这一题是NP-hard，但是分析一下结果那么大，还让取模，必然不是像背包那样的DP，数据范围卡得很死，也不可能是$O(n^2)$，估计是贪心。但是想半天也没想出来，因为排队接水每个人任务量是固定的，不会等得越多时间越长啊，但考虑一下这个排队接水的本质，就是两个任务交换的代价差和位置无关，那么就算一下交换前后的代价。 考虑两个相邻任务 $i$、$j$, 前方已经处理的总工作量为 $T$。

• 顺序 $i → j$ 的增量：

$p_i = a_i + b_i \times T$

$p_j = a_j + b_j \times (T + p_i)$

• 顺序 $j → i$ 的增量：

$p'_j = a_j + b_j \times T$

$p'_i = a_i + b_i \times (T + p'_j)$

• 时间和的差值：

$(C' − C) = (a_j \times b_i − a_i \times b_j)$

可以观察到这个结果并不包含$T$，那么$i$ 和 $j$ 的相对顺序只取决于$a_i \times b_j \stackrel{?}{\le} a_j \times b_i$，这个和有代价的排队接水是一样的。那么就可以放心贪心了，把这个比较关系作为排序的依据开始模拟即可。复杂度$O(n \log n)$，AC。

#include <cstdio>
#include <algorithm>
#define ll long long
using namespace std;

const ll MOD = 1000000009LL; 

struct Person {
    ll a, b;
}v[10005];
ll n;

bool cmp(const Person &x, const Person &y) {
    return (__int128)x.a * y.b < (__int128)y.a * x.b;
}

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)scanf("%lld%lld", &v[i].a, &v[i].b);

    sort(v + 1, v + n + 1, cmp);

    ll wait = 0;   
    ll ac  = 0;   

    for (auto &p : v) {
        ll cur = ( (p.a % MOD) + (wait % MOD) * (p.b % MOD) % MOD ) % MOD;
        ac = (ac + cur) % MOD;
        wait = (wait + cur) % MOD;  
    }

    printf("%lld", ac % MOD);
    return 0;
}