处女座的训练（贪心+结构体排序）

忘是亡心i 2022-03-22 07:00 180阅读 0赞

链接：[https://ac.nowcoder.com/acm/contest/329/D][https_ac.nowcoder.com_acm_contest_329_D]  
来源：牛客网

处女座靠着自己的家教本领赚够了去比赛的钱，于是开启了疯狂训练。在每个夜深人静第二天不收作业的夜晚，他都会开始刷题。  
  
"今日又是一个刷题的夜晚。"他挑选了n道题开始刷，而题太多，刷不掉，理还乱（呜呜）、自己没有解决的题目每分钟都会给他带来bibi的疲倦值，而解决每一道题目都需要花费aiai分钟的时间。  
  
当然，处女座一般都是考虑清楚了再写题的，所以他在写题的时候都会精神抖擞，也就是说，当前正在写的那一题并不会给他带来任何疲劳。  
  
为了迎接后天要收的作业和明天要遇到的小姐姐，他想让今晚的刷题尽可能的轻松，那请你帮他找出最小所需要的疲倦值吧。

## 输入描述: ##

输入数据共包括n+1行，第一行包括一个n表示处女座今晚打算训练的题的数量。
    
    接下来n行，每行包括两个整数ai,biai,bi，分别表示处女座刷掉本题要花费的时间和本题每分钟会带来的疲倦值。

## 输出描述: ##

一行包括一个整数，表示处女座今晚训练会产生的最小疲倦值。

示例1

## 输入 ##

复制

6
    6 1
    4 5
    4 3
    6 2
    8 1
    2 6

## 输出 ##

复制

## 说明 ##

先做第6个题，增加（1+5+3+2+1）*2= 24 点疲倦值，再做第2个题，增加28点疲倦值，随后依次是第3,4,1,5道题，增加16,12,6点疲倦值。总共的疲倦值是24 + 28 + 16 + 12 + 6 = 86点。

## 备注: ##

2≤N≤1052≤N≤105.
    2≤ai≤4⋅1062≤ai≤4⋅106.
    1≤bi≤1000

> 贪心题，结构体排序，不过要注意排序条件。

#include<iostream>
    #include<map>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    typedef long long LL;
    
    struct AC
    {
    	LL x,y;
    }a[100000+10];
    
    bool cmp(AC a,AC b)
    {
    	if (a.x*b.y<b.x*a.y)  
    	return true;
    	if (a.x*b.y==b.x*a.y)
    	return a.x<b.x;
    	else 
    	return false;
    }
    
    int main()
    {
    	LL n,m,j,k,i,T;
    	cin>>n;
    	
    	for (i=0;i<n;i++)
    	{
    		cin>>a[i].x>>a[i].y;
    	}
    	
    	sort(a,a+n,cmp);
    	
    	for (i=n-1;i>=0;i--)
    	{
    		if (i!=n-1)
    		a[i].y = a[i].y +a[i+1].y;
    	}
    	
    	
    	/*for (i=0;i<n;i++)
    	cout<<a[i].x<<" "<<a[i].y<<endl;*/
    	
    	LL ans=0;
    	for (i=0;i<n-1;i++)
    	{
    		ans += (a[i].x*a[i+1].y);
    	}
    	cout<<ans<<endl;
    	
    	return 0;
     }

[https_ac.nowcoder.com_acm_contest_329_D]: https://ac.nowcoder.com/acm/contest/329/D