【问题描述】

        小明一共有n项作业，第i项作业要在di时间之前完成，小明完成第i项作业需要bi的时间，对于小明来说，喝奶茶可以提高工作效率，但是奶茶对于不同的作业功效是不同的，你可以认为，小明在做第i项作业期间，每喝1ml的奶茶，他完成第i项作业所需要的时间就会减少ai，当然，奶茶还不至于神奇到有时间倒流的功能。

        现在，小明想知道，他要按时完成所有作业最少要喝奶茶的毫升数。

【输入格式】

        第一行一个正整数；

        接下来n行每行三个正整数ai,bi,di;

【输出格式】

        输出一个小数，表示小明要按时完成所有作业最少要喝奶茶的毫升数。（保留两位小数）

【输入样例】

        2 

        20 50 100

        10 100 50

【输出样例】

          5.00

【数据范围】

对于20%的数据，n<=10，对于所有的i满足di<=100,ai=1;

对于40%的数据,n<=3000;

对于100%的数据,1<=n<=2*10^5.ai,bi,di<=10^6

【算法分析】

        首先，有一个很显然的结论：如果做了若干项作业，它们的相对顺序对后面的作业是没有影响的，所以我们可以先把作业按截至时间排序从前往后做。

        依次枚举作业，如果当前不喝奶茶单纯完成时间来不及，就吵之前做过的ai最大且bi>0作业不断喝，直到时间充足。

由于前面算法的瓶颈在于找ai最大，我们直接用堆来维护一下最大值就可以通过本题了（当然你也可以使用任何支持查询最大值的数据结构，比如线段树）‘

时间复杂度（nlogn）

【核心代码1】

sort(p+1,p+n+1,cmp);
for(ont i=1;i<=n;++i)
{
	tot+=p[i].b;Q.Push(i);
	if(tot>p[i].d)
	{
		while(tot-p[i].d>=p[top=Q.g[1]b])
		{
			Ans+=p[top].b/(double)p[top].a;
			tot-=p[top].b;Q.Pop();
		}
		if(tot-p[i].d>0)
		{
			Ans+=(tot-p[i].d)/(double)p[top].a;
			p[top].b-=tot-p[i].d;tot=p[i].d;
		}
	}
}

’【核心代码2】

struct heap{
	int g[m],len;
	inline void push(const int &res){
		g[++len]=res;
		int now =len,nxt=len>>1;
		while (nxt){
			if(p[res].a>p[g[nxt]].a)
			g[now]=g[nxt],nxt=(now=nxt)>>1;
		}
		g[now]=res;
	}
}
inline void pop(){
	g[i]=g[len--];
	while(nxt<=len){
		if(nxt<len && p[g[nxt[1]]].a>p[g[nxt]].a) naxt|=1;
		if(p[g[nxt]].a>p[res].a)
		g[now]=g[nxt],nxt=(now=nxt)<<1;
	}
	g[now]=res;
}Q;

int main(){
	n=get();Q.len =0;
	for(int i=1;i<=n;++i){
		p[i].a=get();
		p[i].b=get();
		p[i].d=get();
	}
	sort(p+1,p+n+1,cmp);
	for(int i=1;i<=n;++i){
		tot+=p[i].b;Q.push(i);
		if(tot>p[i].d){
			while (tot-p[i].d>=p[top=Q.g[1]].b)
			{
				Ans +=p[top].b/(double)p[top].a;
				tot-=p[top].b;Q.pop();
			}
			if(tot-p[i].d)>0{
				Ans+=(tot-p[i].d)/(double)p[top].a;
				p[top].b-=tot-p[i].d;   tot=p[i].d;
			}		
			
		}
	}
	printf("%.2lf\n",Ans);
	return 0;
	
}