当前位置：首页 > article >正文

【题解】AT_arc035_b [ARC035B] アットコーダー王国のコンテスト事情

article 2024/9/20 13:33:49

原题传送门

思路分析

第一问

考虑贪心，不难想到要先完成所用的时间少的，因为每道题所用的时间都会累加到后面的题目的罚时中，前面的用时会对后面的罚时产生影响。

贪心排完序后按题意模拟即可，注意要开 long long。

第二问

根据第一问，不难证明最优开题顺序肯定是唯一的，即开题顺序不能改变，因为任意两道题所需要的时间可能相同（这也是为什么会有开题顺序总数），所以我们可以交换所需要的时间相同的两道题的先后顺序。

考虑排列组合，设 $n$ 表示当前相同的题数，求 $n$ 个数调换顺序组成的方案数不就是小学学过的 全排列 问题吗，方案数很明显为 $n!$ ，记得对 $10^9+7$ 取模。

注意 Atcoder 题输出最后要换行。

$\texttt{code}$

/*Written by smx*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN=1e4+5,inf=1e18,mod=1e9+7; 
int t[MAXN],cnt[MAXN];
int f(int n){
	int ret=1;
	for(int i=2;i<=n;i++){
		ret=(ret*i)%mod;
	}
	return ret;
}
signed main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n,Time=0,maxn=INT_MIN,ans1=0,ans2=1;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>t[i];
		maxn=max(maxn,t[i]);
	}
	sort(t+1,t+n+1);
	for(int i=1;i<=n;i++){
		Time=Time+t[i];
		cnt[t[i]]++;
		ans1=ans1+Time;
	}
	for(int i=1;i<=maxn;i++){
		if(cnt[i]>0){
			ans2=(ans2*f(cnt[i]))%mod;
		}
	}
	cout<<ans1<<"\n"<<ans2<<"\n";
	return 0;
}