The Lazy Programmer

题目描述

A new web-design studio, called SMART (Simply Masters of ART), employs two people. The first one is a web-designer and an executive director at the same time. The second one is a programmer. The director is so a nimble guy that the studio has already got $N$ contracts for web site development. Each contract has a deadline $d_i$.

It is known that the programmer is lazy. Usually he does not work as fast as he could. Therefore, under normal conditions the programmer needs $b_i$ of time to perform the contract number $i$. Fortunately, the guy is very greedy for money. If the director pays him $x_i$ dollars extra, he needs only $(b_i-a_ix_i)$ of time to do his job. But this extra payment does not influent other contract. It means that each contract should be paid separately to be done faster. The programmer is so greedy that he can do his job almost instantly if the extra payment is $(b_i/a_i)$ dollars for the contract number $i$.

The director has a difficult problem to solve. He needs to organize programmer’s job and, may be, assign extra payments for some of the contracts so that all contracts are performed in time. Obviously he wishes to minimize the sum of extra payments. Help the director!

题意概述

有$N$个合同，第$i$个合同需要在时刻$d_i$前完成。程序员完成第$i$个合同所需的时间为$b_i$，若给他$x_i$元钱则他完成这个合同所需的时间会减少$a_ix_i$（但不会小于$0$）。求在按时完成所有合同的前提下所需的最少钱数。

数据范围：$1 \le N \le 10^5, \ 1 \le a_i, b_i \le 10^4, \ 1 \le d_i \le 10^9$。

算法分析

首先完成合同的顺序是确定的，即先将所有合同按$d_i$从小到大排序。

接下来我们依次处理合同。如果发现第$i$个合同无法按时完成，那么就从之前已经完成的合同中找一个$a_j$最大的，给这个任务付钱（当然，要保证$b_j$不小于$0$）。

建一个大根堆，维护已经完成合同的$a_i$，同时维护当前耗时$t$。当处理第$i$个合同时发现$t \gt d_i$，就给堆顶合同付钱直到$t \le d_i$；若堆顶合同的$b_j=0$，则将它从堆中移出。

时间复杂度为$O(N\log N)$。

代码

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int n, t;
double ans;
struct contract {
    int a, b, d;
    bool operator < (const contract &t) const {
        return a < t.a;
    }
} c[100001];
bool cmp(contract a, contract b) {
    return a.d < b.d;
}
priority_queue<contract> q;
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d%d%d", &c[i].a, &c[i].b, &c[i].d);
    }
    sort(c + 1, c + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        q.push(c[i]);
        t += c[i].b;
        if (t > c[i].d) {
            int delta = t - c[i].d;
            while (delta) {
                contract tmp = q.top();
                q.pop();
                if (tmp.b < delta) {
                    delta -= tmp.b;
                    ans += tmp.b * 1.0 / tmp.a;
                } else {
                    tmp.b -= delta;
                    ans += delta * 1.0 / tmp.a;
                    delta = 0;
                    q.push(tmp);
                }
            }
            t = c[i].d;
        }
    }
    printf("%.2lf\n", ans);
    return 0;
}