每日一题：Protecting the Flower （贪心）

题意

一共有 $n$ 只牛在花坛旁边，第 $i$ 头牛每分钟破坏 $d_i$ 朵花，把第i头牛带回牛棚需要 $2 \times ti$ 这么多时间，每次只能带回一头牛，请问怎样能使得被破坏的花最少。

solution

以小化大，先考虑两头牛，先领 $a$ ，损失为：$2\times{t_a}\times{d_b}$，先领 $b$，损失为 $2\times{t_b}\times{d_a}$，故得到排序条件 ${a_t \times {b_d} < b_t \times {a_d}}$，最后模拟得出答案。

Code

#include <bits/stdc++.h>
#define x first
#define y second
#define PI pair<int, int>
#define ll long long
using namespace std;
ll n, sum, res;
pair<int, int> p[200005];
int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> p[i].x >> p[i].y;
  sort(p + 1, p + n + 1, [](PI a, PI b) { return a.x * b.y < b.x * a.y; });
  for (int i = 1; i <= n; i++) {
    res += sum * p[i].y;
    sum += p[i].x * 2;
  }
  cout << res << '\n';
  return 0;
}