AtCoder – 4846 – Max-Min Sums

$\rm{Description}$

给定 $n$ 个数,构成集合 $A$。从 $A$ 中任取 $k$ 个数,构成 $A$ 的子集 $S$.

记 $\rm{Max}$ 为 $S$ 中的最大值,$\rm{Min}$ 为 $S$ 中的最小值,$f(S)=\rm{Max-Min}$.

题目要求:所有满足 $|S|=k$ 的 $f(S)$ 之和。(对 $1e9+7$ 取模)

$\rm{Solution}$

观察数据范围,期望时间复杂度为: $\mathcal{O}(n\log n)$ 或者 $\mathcal{O}(n\log |x|)$ 的做法。

暴力的方法就是 $C_n^k$ 枚举元素个数为 $k$ 的子集,然后找最大值和最小值,复杂度爆炸,期望得分 $0$ 分.

考虑集合的无序性

将集合内的元素升序排序,之后发现可以计算每个数可能在多少个子集中成为最大值/最小值

考虑如何统计作为子集中最大值的次数

具体地,对于前 $k – 1$ 个数,不可能成为任何一个子集的最大值;对于其余的数,第 $i$ 个数成为最大值的方法数是 $C_{i-1}^{k-1}$ 种,也就是在前 $i-1$ 个数中取 $k-1$ 个,与第 $i$ 个数一起构成子集,这样的子集能使 $i$ 为最大值。

for(int i = k; i <= n; i++) { //算一遍最大值
	ans += a[i] * C(i - 1, k - 1);
}
//为了美观,这里的代码没有取模。下面Code部分的代码有取模。

对于统计作为子集中最小值的次数,与最大值同理。

for(int i = 1; i <= n - k + 1; i++) { //算一遍最小值
	ans -= a[i] * C(n - i, k - 1);
}
//为了美观,这里的代码没有取模。下面Code部分的代码有取模。

在这个数据范围下,使用逆元求组合数就可以了,如果不会用逆元求组合数,可以看一下我写的这篇博客,往下翻,可以找到关于组合数取模的部分。

$\rm{Code}$

给出完整的代码。

#include <bits/stdc++.h>
#define int long long
#define MAXN 100008
using namespace std;
int mod = 1e9 + 7;
int n, k, a[MAXN], fac[MAXN], ans = 0;
int power(int x, int k, int p) {
	int ret = 1;
	while(k) {
		if(k & 1) ret = ret * x % p;
		k >>= 1;
		x = x * x % p;
	}
	return ret % p;
}
int inv(int x, int p) {//求x关于模p的逆元
	return power(x, p - 2, p) % mod;
}
int C(int a, int b) {//直接用逆元求解组合数C(a, b)
	return fac[a] * inv(fac[b], mod) % mod * inv(fac[a - b], mod) % mod;
}
signed main() {
	scanf("%lld%lld", &n, &k);
	for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
	fac[0] = 1;
	for(int i = 1; i <= n; i++) fac[i] = fac[i - 1] * i % mod;
	sort(a + 1, a + n + 1); //升序排序
	//对于每个数,计算在多少种个子集中,这个数能作为最大值/最小值
	//作为最大值的可能情况是C(i - 1, k - 1),最小值类似
	for(int i = k; i <= n; i++) { //算一遍最大值
		ans = (ans + a[i] * C(i - 1, k - 1) % mod) % mod;
	}
	for(int i = 1; i <= n - k + 1; i++) { //算一遍最小值
		ans = (ans - a[i] * C(n - i, k - 1) % mod) % mod;
	}
	cout << (ans % mod + mod) % mod << endl;
	return 0;
}

评论

  1. MasonWang
    Windows
    2年前
    2021-1-02 21:23:56

    %%%%

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇