20221015 zzsz模拟赛第一轮
author: zzafanti(FreshOrange)
请勿转载
总述
作为zzsz上线OJ以来的第一场比赛，不出意外地出了些意外。比赛必须在开始前报名，这使得一些同学痛失准时参赛机会。
学校紧急又建了一个重建赛，\(15:30\)开始,做出了一个补救。
这也提醒我们：准时报名！！！！！！！ （注意csp是否缴费）;
\(print\)("准时是对守时的尊重。——\(Miss Llj\)")
这次比赛难度较为一般，思维难度不是非常大，努努力把控好细节\(300pts+\) 应该是会太难的。
鹅而我\(T2\)挂了……
\(T2\)明显的思维漏洞，没有发现（其实很好举出反例（虽然希望下次比赛可以给大样例QwQ））
\(T3\)挂了\(50pts\)，考虑到确实对自己的想法没啥把握，这个扣分也在可接受范围内吧……
(注意：题目难易顺序从简到繁依次大概是 T4,T2,T1,T3，这也是一个可以参考的做题顺序)
共20多名同学参赛
\(T4\) A掉了6人，一个“排队接水”型贪心的板题。
\(T2\) A掉3人，但是有两人代码完全相同……这……
\(T1\) A掉1人，有几个 \(TLE\) 3个点的同学。
\(T3\) 最高\(50pts\),其他是骗分……
题解
\(T4\) -拍照（注意！题目1~4并非安难易排序）
问题描述：
ZZSZ是个美丽的学校，有很多值得拍照记录的地方。有一天，你和你的小伙伴来到了ZZSZ美丽的校园，有一处很有纪念意义的地方，你们都想拍照记录。总共有\(N\)个人，大家排好队，一个个去拍照。每个人拍照的时间是不一样的，有的想拍成艺术照珍藏，有的只是想表明到此一游。
为了节省大家的时间，请你设计一个排队方案，让所有人等待的时间总和最少。
输入格式：
第一行一个整数\(N\)，表示有\(N\)个同学。
第二行包含\(N\)个整数，表示每个人的拍照时间。
输出格式：
输出所有人等待时间的最小值。
输入样例：
5
2 3 1 5 4
输出样例：
20
数据范围
对于 100%的数据满足：\(1\leq N\leq50000\)，每个人的等待时间小于等于\(100000\)。
分析
以\(a_i\)表示第\(i\)个人接水的时间
则对于\(p\)(\(1\leq p \leq n-1\)),\(a_p\)与\(a_{p+1}\)对答案的贡献为
\(a_p*(n-p)+a_{p+1}*(n-p-1)\)
显然 \(n-p>n-p-1\)
若 \(a_{p+1}\leq a_p\)
\(a_p*(n-p)+a_{p+1}*(n-p-1)\)一定大于等于\(a_{p+1}*(n-p)+a_p*(n-p-1)\)
即，将相邻两项中的较小数排在前，可保证这两数对答案贡献最小
考虑整个序列\(a\),
只需将其从小到大排序，依次计算每一项对答案的贡献，求和即可
记得开long long
时间复杂度\(O(nlogn)\),瓶颈在排序
参考代码
typedef long long ll;
const int N=50100;
ll a[N],n,res;
void solve(){
cin >> n;
for(int i=0; i<n; i++) scanf("%d",&a[i]);
sort(a,a+n);
for(int i=0; i<n-1; i++){
res+=a[i]*(n-i-1);
}
cout<< res<<endl;
}
update: 20221017
标签：拍照,zzszoi20221015,T4,T2,T3,long,leq From： https://www.cnblogs.com/FreshOrange/p/16801167.html