代码源, 博客

题目描述

又到了 H 国国庆, 国王再次邀请 n 位大臣来玩有奖游戏。上次国庆被众臣吐槽国王小气后，国王决定今年大方点，改变游戏规则且不再参与游戏，免得被大臣们质疑。首先, 他让每位大臣在左、 右手上面分别写下一个正整数。然后让这 n 位大臣排成一排。排好队后, 所有的大臣都会获得国王奖赏的若千金币, 每位大臣获得的金币数分别是：排在该大臣后面的所有人的左手上的数的乘积乘以他自己右手上的数。国王希望所有大臣获得的金币数之和最多，所以他想请你帮他重新安排一下队伍的顺序。

简而言之，给定 n 对数 ai,bi，找到一种排列顺序，使得 $b_1 \cdot \prod_{i=2}^{n}a_i + b_2 \cdot \prod_{i=3}^{n}a_i … + b_n$ 最大，求最大值，由于答案可能很大，需要对 1000000007 取模

输入格式

第一行，包含一个整数 n。 第二行到第 n+1 行，包含两个整数 $a_i, b_i$

输出格式

输出一行，表示按某种排序后的 $b_1 \cdot \prod_{i=2}^{n}a_i + b_2 \cdot \prod_{i=3}^{n}a_i … + b_n$ 的最大值对 1000000007 取模的结果

思路

先说结论: 对$\frac{a_i - 1}{b_i}$从小到大排序

证明:
对于相邻的两个人${a_i, b_i}$和${a_{i+1}, b_{i+1}}$

• 交换前: $\prod_{j=i+1}^{n}a_j \cdot b_i + \prod_{j=i+2}^{n}a_j \cdot b_{i+1}$

• 交换后: $\prod_{j=i+2}^{n}a_j \cdot a_i \cdot b_{i+1} + \prod_{j=i+2}^{n}a_j \cdot b_{i}$

于是可以同时约去$\prod_{j=i+2}^{n}a_j$, 得

$a_{i+1} \cdot b_i + b_{i+1}$同$a_{i} \cdot b_{i+1} + b_{i}$

移项并同除得, $\frac{a_{i+1}-1}{b_{i+1}}$同$\frac{a_{i}-1}{b_{i}}$

对于该式, 若要使得答案最大, 则不等式左侧应该较大, 所以 应对$\frac{a_i - 1}{b_i}$从小到大排序. 证毕.

代码

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1e6 + 10, mod = 1e9 + 7;

int n;
struct Node {
    LL a, b;
    double c;
}a[N];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) {
        scanf("%lld%lld", &a[i].a, &a[i].b);
        a[i].c = (a[i].a - 1) * 1.0 / a[i].b;
    }
    sort(a + 1, a + n + 1, [](Node a, Node b) {
        return a.c < b.c;
    });

    a[n + 1].a = 1;
    for (int i = n; i >= 1; i -- ) {
        a[i].a = a[i].a * a[i + 1].a % mod;
    }

    LL ans = 0;
    for (int i = 1; i <= n; i ++ ) {
        ans = (ans + a[i].b * a[i + 1].a) % mod;
        //cout << ans << endl;
    }
    printf("%lld\n", ans);
    return 0;
}