问题 B: 奎奎发红包

时间限制: 1 Sec  内存限制: 128 MB
提交: 2489  解决: 390
[状态] [提交] [命题人:外部导入]

题目描述

情人节又到了，又到了一年一度发红包的时间。经大家研究决定，今年让奎奎自愿发红包。
俱乐部有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]。

输出

一个整数表示答案。

样例输入 Copy

4
1 4
2 3
3 2
4 1

样例输出 Copy

35

 

题意：略

思路：按v / t比值从大到小排序，注意0的存在，u1s1，我没有管0也A了？但是多组样例输入就WA了？

 

有没有人告诉我为什么加上多组样例输入就WA？？？？？？？？？？

三个人死磕了3小时再见吧您 为了净化我的博客我还是别写脏话了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10;

struct node
{
    int v, t;
    double k;
} s[N];

bool cmp(node x, node y)
{
    return x.k > y.k;
}

int main()
{
    int n, tot = 0, vv, tt;
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
    {
        scanf("%d%d", &vv, &tt);
        if(vv && tt)
        {
            tot++;
            s[tot].v = vv;
            s[tot].t = tt;
            s[tot].k = 1.0 * vv / tt;
        }
    }
    sort(s + 1, s + tot + 1, cmp);
    ll ans = 0;
    ll t = 0;
    for(int i = 1; i <= tot; ++i)
    {
        t += (ll)s[i].t;
        ans += (ll)s[i].v * t;
    }
    cout<<ans<<'\n';
    return 0;
}