3D.处女座的训练（C++）

处女座的训练（C++）

点击做题网站链接

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

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

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

示例1
输入
6
6 1
4 5
4 3
6 2
8 1
2 6

输出
86

说明
先做第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≤10^5$
$2≤a_i≤4⋅10^6$
$1≤b_i≤1000$

题目分析：
贪心思想。按照$frac{a_i}{b_i}$作为关键字进行排序，按顺序完成作业即可。

解题代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e+5;
struct st
{
    int a;//刷掉本题要花费的时间
    int b;//本题每分钟会带来的疲倦值
}questions[N];

bool cmp(st x, st y)
{
    return x.a*y.b < x.b*y.a;
}

int main()
{
    int n;
    cin >> n;
    long long ans=0,sum=0;
    for(int i=0;i<n;++i)
    {
        cin >> questions[i].a >> questions[i].b;
        sum += questions[i].b;
    }
    sort(questions,questions+n,cmp);
    for(int i=0;i<n;++i)
    {
        sum -= questions[i].b;
        ans += sum*questions[i].a;
    }
    cout << ans << endl;
}

错误解法：

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e+5;
struct st
{
    int a;//刷掉本题要花费的时间
    int b;//本题每分钟会带来的疲倦值
}questions[N];

bool cmp(st x, st y)//两者唯一区别在于排序的不同，这边是先从小到大排a，如果a一样，则从大到小排b，这种排序是错误的
{
    if(x.a<y.a) return true;
    else
    {
        if(x.a==y.a)
        {
            if(x.b>=y.b)
                return true;
        }
    }
    return false;
}

int main()
{
    int n;
    cin >> n;
    long long ans=0,sum=0;
    for(int i=0;i<n;++i)
    {
        cin >> questions[i].a >> questions[i].b;
        sum += questions[i].b;
    }
    sort(questions,questions+n,cmp);
    for(int i=0;i<n;++i)
    {
        sum -= questions[i].b;
        ans += sum*questions[i].a;
    }
    cout << ans << endl;
}