/牛牛吃花花是一道很妙的贪心
核心思路:简单排序+前缀和
由题目可知,有的牛牛虽然说回去的时间少但是战斗力并不高(战斗力指干饭能力)
而有的牛牛则刚好与之相反,所以这个时候如果就考虑送回去的时间来贪心的话就不够贪
为了达到足够的贪就得利益最大化。
经过亿会儿的思考,我们可以得出一个关系式子,2 * t1 * d2与2 *t2 * d1比较
可推出=》ti/di与ti+1/di+1进行比较,我们就称之为牛牛的毁灭性;
就可以得出谁先回去的结论。所以这个时候呢,我们就建立一个方便使用的结构体
用来存储这头牛牛的信息
/
#include <iostream>//为什么头文件就没了呢???iostream
#include <algorithm>//为什么头文件就没了呢???algrithm
using namespace std;
#define N 10000000
struct pp{
int b;
int d;
double e;
} s[N];//结构体可同时存下牛牛回去所需时间,牛牛的干饭能力, 以及牛牛的毁灭性;
bool cmp(pp a,pp b){
return a.e<b.e;
}//快排,按照 毁灭性进行排序,毁灭性最强的自然排在最前面;
int sum[N];
int main(){
int n,x,y;
cin>>n;
for(int i=1;i<=n;i++){
cin>>x>>y;
s[i].b=x;
s[i].d=y;
s[i].e=x*1.0/y;
}
sort(s+1,s+n+1,cmp);</algorithm></iostream>

for(int i=1;i<=n;i++){
sum[i]=sum[i-1]+s[i].d;
}//前缀和,因为当送前面的牛牛回去的时候剩下的所有的牛牛都会吃,所以就可以利用前缀和来优化一手

long long int ans=0;
for(int i=1;i<=n;i++){
ans+=(sum[n]-sum[i])s[i].b2;//用前缀和就可以用 (sum[n]-sum[i])s[i].b2表示当第i头牛牛回去时剩下的牛牛吃掉的;
s[i].b是第i头牛牛走的时候所需要的时间;
}
cout<<ans<<endl;
return 0;
}