【题解】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;
}

原文地址：https://blog.csdn.net/shimingxin1007/article/details/142308657

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！