【题意】就是有n件工作，每件工作有一个期限d，一个预计完成需要的时间 b，还有一个a （如果你给这个人x元，那么他完成这件工作的时间就变为b - a * x。题目所求是问你最少需要多少时间，便可以保证所有工作都在其期限之前完成。

【题解】

我们肯定是按照d从小到大考虑，每次如果能在期限之前完成就不用花钱，很明显如果不能，我们从前面完成的任务中选出一个a最大的（当x相同时，能够省下更多时间）来花钱减时间即可。用堆维护最大最小值。

POJ上不能用“%lf”，要用“%f”，真是坑QAQ

# include <stdio.h>
# include <queue>
# include <algorithm>
using namespace std;

struct node {
	int a, b, d;
	double cost;
	node() {cost=0;}
	friend bool operator <(node A, node B) {
		return A.a<B.a;
	}
} p[100100];
int n;

const double eps = 1e-9, meps = -eps;

inline bool cmp(node a, node b) {
	return a.d<b.d;
}


priority_queue<node> q;

inline bool bzero(double x) {
	return x > eps;
}


int main() {
	scanf("%d", &n);
	for (int i=1; i<=n; ++i) {
		scanf("%d%d%d", &p[i].a, &p[i].b, &p[i].d);
		p[i].cost=0;
	}
	sort(p+1, p+n+1, cmp);
	while(!q.empty()) q.pop();
	double cur=0, ans=0;
	for (int i=1; i<=n; ++i) {
		q.push(p[i]);
		cur += p[i].b;
		while(bzero(cur - p[i].d)) {
			node t = q.top(); q.pop();
			double x = (cur - p[i].d) / t.a;
			if(bzero((double)t.b / t.a - t.cost - x)) {
				t.cost += x;
				ans += x;
				cur -= x*t.a;
				q.push(t);
				break;
			} else {
				x = (double)t.b/t.a - t.cost;
				t.cost += x;
				ans += x;
				cur -= x*t.a;
			}
		}
	}
	printf("%.2f\n", ans);
	return 0;
}