protect the flowers

思路

也是一个推公式的题目

但是发现好像直接推, 有地方化简不了?

这里要用到数学归纳法

先尝试规模为1的子问题

发现好像已经得到递推式了

然后规模为k的问题是最优解, 那么k + 1 也是最优解

对了,要有一个前缀和, 因为是累加

ac代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const int inf = INT_MAX;
typedef pair<int, int> pii;
typedef priority_queue<int, vector<int>, greater<int>> small_heap;
#define int long long
#define dd first
#define tt second
bool cmp(const pii &a, const pii &b)
{
    return 1.0 * a.tt / a.dd < 1.0 * b.tt / b.dd;
}
int32_t main()
{
    int n;
    cin >> n;
    vector<pii> a(n + 1);
    vector <int>  sd(n + 1);
    for (int i = 1; i <= n; i++)
    {
        int t, d;
        cin >> t >> d;
        a[i] = {t, d};
    }
    sort(a.begin() + 1, a.end(), cmp);
    int sum = 0;
    sd[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        sd[i] = sd[i - 1] + a[i].dd;
    }
    for (int i = 1; i <= n; i++)
    {
        sum +=(sd[n] - sd[i]) * a[i].tt * 2;
    }
    cout << sum;
    return 0;
}