[ARC035B] アットコーダー王国のコンテスト事情题解-526互联

前置芝士

排列组合

分析

明显的贪心，第一问与此题思路相似，优先选择做时间少的，可以尽可能让后面的罚时尽量的小。

难点在第二问，第二问问的是有几种可能性，有个显然的结论：

相同做题时间的题目，位置调换答案仍然相同。

那么可以用桶+排列组合来解决：

用桶储存这个做题时间的出现次数 \(b_i\)，然后进行遍历，如果这个数出现多次，那么 \(ans = ans \times b_i!\)。

注意输出答案时，结尾要有换行。~~AT 老 bug 了~~。

Accpeted Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e4 + 5;
const int mod = 1e9 + 7;
int t[N], b[N], now, mx, ans1, ans2 = 1;
int fac(int n)
{
	int res = 1;
	for (int i = 1; i <= n; i++)res = (res * i) % mod;
	return res;
}
signed main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> t[i];
	sort(t + 1, t + n + 1);
	for (int i = 1; i <= n; i++)
	{
		now += t[i];
		mx = max(mx, t[i]);
		b[t[i]]++;
		ans1 += now;
	}
	for (int i = 1; i <= mx; i++)
		if (b[i])ans2 = (ans2 * fac(b[i])) % mod;
	cout << ans1 << endl << ans2 << endl;
	return 0;
}