题目:
情人节又到了,又到了一年一度发红包的时间。经大家研究决定,今年让奎奎自愿发红包。
俱乐部有n个人(0<n<100000),每个人都有一个单身值v[i]与亲密度ti,单身值越大的人,在情人节的时候就越羡慕奎奎,奎奎就需要给他更大的红包来安慰他。 由于一个寒假没有见到奎奎,领红包的时候大家都想跟奎奎py,花费时间t[i],先py后给红包噢。
大家都厌倦了等待,如果一个人等了时间t,那么奎奎发给他的红包大小就是v[i]·t。
但是奎奎还要和女朋友去快乐,想要花最少的钱来满足大家。
请你帮他计算最少需要发多少钱的红包。
输入
第一行一个整数n。接下来n行,每行两个数v[i]和t[i]。
输出
一个整数表示答案。

尝试贪心确定顺序,使用邻项交换法
a.v*(T+a.t)+b.v*(T+b.t+a.t)<b.v*(T+b.t)+a.v*(T+a.t+b.t)
一定要化简啊!
–>a.tb.v<a.vb.t
–>a.t/a.v<b.t/b.v
(再特别处理一下a.v==0时)

~~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T=0;
struct node{
   
	double v;
	double t;
	double x;
}a[100001];
int cmp(node a, node b){
   
	return a.x<b.x;
}
int main()
{
   
	ll n;
	scanf("%lld", &n);
	for(ll i=1; i<=n; i++) {
   
		scanf("%lf%lf", &a[i].v, &a[i].t);
		if(a[i].v!=0)
			a[i].x=a[i].t/a[i].v;
		else
			a[i].x=0;
	}
	sort(a+1,a+n+1,cmp);
	ll ans=0;
	for(int i=1; i<=n; i++) {
   
		ans+=(T+a[i].t)*a[i].v;
		T+=a[i].t;
	}
	printf("%lld\n",ans);
	return 0;
}