UPCOJ 1116 奎奎发红包

题目描述

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

输入

第一行一个整数 $n$ 。接下来 $n$ 行，每行两个数 $v[i]$ 和 $t[i]$ 。

输出

一个整数表示答案。

样例输入

4
1 4
2 3
3 2
4 1

样例输出

思路

先来解释一下样例。
$(1,4)$ 先py，然后等着；接着 $(2,3)$ py，然后等着；接着 $(3,2)$ py，然后等着；最后 $(4,1)$ py。需要付出的总钱数:

$total=4\times 1+3\times \left(2+1\right)+2\times(3+2+1)+1\times(4+3+2+1)=35$

对于两个人 $a,b$ ，排序时要将花费少的排序在前面，也就是判断

$a.v\times a.t+b.v\times (a.t+b.t)<b.v\times b.t+a.v\times (a.t+b.t)$

化简后为

$a.t\times b.v<b.t\times a.v$

如果两者相等，那么 $v$ 小的要排在前面，然后进行一次前缀和操作得到每个人等待的时间即可（注意不要爆int）。

代码

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
const int N=100003;
struct node
{
	ll v;
	ll t;
}person[N];
int n;
bool cmp(node a,node b)
{
	if(a.t*b.v==b.t*a.v) return a.v<b.v;
	else return a.t*b.v<b.t*a.v;
}
void solve()
{
	cin>>n;
	int i;
	for(i=1;i<=n;i++) cin>>person[i].v>>person[i].t;
	sort(person+1,person+1+n,cmp);//排序
	for(i=2;i<=n;i++) person[i].t=person[i].t+person[i-1].t;//前缀和操作
	ll ans=0;
	for(i=1;i<=n;i++) ans+=person[i].v*person[i].t;
	cout<<ans; 
}
int main()
{
	solve();
	return 0;
}