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

原题传送门

---

思路分析

第一问

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

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

第二问

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

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

---

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

$\text{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;
}