[Daimayuan]新国王游戏（C++，数学）-Toy模板网

这篇具有很好参考价值的文章主要介绍了[Daimayuan]新国王游戏（C++，数学）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

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

简而言之，给定 $n$ 对数 $a_i,b_i$ ，找到一种排列顺序，使得 $b_1×a_2∗a_3∗…a_n+b_2×a_3∗a_4∗…a_n+⋯+b_n$ 最大，求最大值，由于答案可能很大，需要对 $1000000007$ 取模

输入格式：

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

输出格式:

输出一行，表示按某种排序后的 $b_1×a_2∗a_3∗…a_n+b_2×a_3∗a_4∗…a_n+⋯+b_n$ 的最大值对 $1000000007$ 取模的结果

样例输入

2
1 2
3 4

样例输出

说明

只有两种情况：

$1.$

1 2
3 4

$(2 * 3) + 4 = 10$

$2.$

3 4
1 2

$(4 * 1) + 2 = 6 (4 * 1) + 2 = 6$

所以答案为 $10$

数据限制

对于 $100$ % 的数据，保证 $1≤n≤10^6$ , $1≤a_i,b_i≤2^{30}$

解题思路

思路很简单：先排序，然后累加求和

解题关键在于如何排序

采用算法sort()进行排序，我们需要做的就是重载比较运算符，而重载比较运算符，我们就只需要考虑一种简单的比较情形：相邻对换

对于 $i, i + 1$ 两位大臣，我们不需要考虑其 $i$ 前面的人和 $i + 1$ 后面的人，因为他们的顺序是不变的

我们只需要考虑两位大臣调换前后二者获取的金币变多了还是变少了

在调换之前： $b_i*a_{i+1}+b_{i+1}$

在调换之后： $b_{i+1}*a_i+b_i$

比较二者的大小即可知道哪种排序获得的金币更多

AC代码如下文章来源地址https://www.toymoban.com/news/detail-400786.html

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int max_n = 1e6;
const int max_ab = pow(2, 30);
const int mod_num = 1000000007;

struct person { long long l, r; }persons[max_n + 1];

int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> persons[i].l >> persons[i].r;
	sort(persons + 1, persons + 1 + n, [](person p1, person p2) {
		return p1.r * p2.l + p2.r > p2.r * p1.l + p1.r;
		});
	long long ans = 0;
	long long sum = 1;
	for (int i = n; i > 0; i--) {
		ans = (ans + persons[i].r * sum) % mod_num;
		sum = (sum * persons[i].l) % mod_num;
	}
	cout << ans << endl;
	return 0;
}