DDOSvoid's Blog

Luogu P2878 [USACO07JAN]Protecting the Flowers S

发表于 分类于
本文字数： 653 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P2878

Solution

最经典的利用贪心进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <algorithm>
#include <cstdio>
#define maxn 100010
#define cn const node
#define ll long long 
using namespace std;

int n, m;

struct node {
    int d, t;

    node() {}
    node(int _d, int _t) { d = _d; t = _t; }

    friend bool operator < (cn &u, cn &v) { return v.d * 2 * u.t < u.d * 2 * v.t; } 
} a[maxn]; 

ll ans, sum; 
int main() { 
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> a[i].t >> a[i].d, sum += a[i].d;
    sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++i) 
        sum -= a[i].d, ans += 2 * a[i].t * sum;
    cout << ans << endl; 
    return 0;
}