BZOJ3850 ZCC Loves Codefires

2015.01.07 08:46 Wed| 1 visits oi_2015| 2015_刷题日常| Text

Solution

一道英语题,只是存在一点点有趣的推公式过程。

设最优的做题顺序中,第 $p$ 道题编号为 $i$ ,第 $p+1$ 道题编号为 $j$ 。设前 $p-1$ 道题总用时为 $sum$ , 则这两道题用时 $T_1=(sum+t_i)k_i+(sum+t_i+t_j)k_j$ 。若这两道题顺序交换,对其他题目的扣分无影响,这两道题的用时 $T_2=(sum+t_j)k_j+(sum+t_i+t_j)k_i$ 。由题意知 $T_1\le T_2$ 。化简得到 $t_i\times k_j\le t_j\times k_i$ 。根据此式排序即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 100005

struct prob
{
    int a, b;
    bool operator <(const prob &x) const
    {
        return a * x.b < x.a * b;
    }
};

int n;
prob s[N];
long long sum, ans;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for(int i=1; i<=n; i++) cin >> s[i].a;
    for(int i=1; i<=n; i++) cin >> s[i].b;
    sort(s+1, s+n+1);
    for(int i=1; i<=n; i++)
        sum += s[i].a, ans += sum * s[i].b;
    cout << ans << endl;
    return 0;
}