题解 CF1117B 【Emotes】
justinjia
2021-01-17 21:17:00
这是一道比较水（你看这题难度不就是水的颜色吗）的小学奥数题（考察知识点：周期问题）。。。
[此题解在题解区域食用更佳（原因：我那个表格在博客里貌似显示不出来）](http://www.luogu.com.cn/problem/solution/CF1117B)
首先搭上框架：
```cpp
#include"stdio.h"//我习惯这么写
#include"algorithm"
using namespace std;
#define int long long//根据本题的数据范围，需要开long long
signed main(void){//signed等同于int，如果还写int main(void)的话就相当于long long main()，会CE
int n,m,k,a[200000];
scanf("%lld%lld%lld",&n,&m,&k);//别忘了我们这是long long，我曾经因为占位符写错而被卡了N次
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
sort(a,a+n);
```
接下来，你可能会用循环来累加每次选择的表情，但是这样会$\colorbox{darkblue}{\color{white}TLE}$。
那该怎么办呢？
就像我第一句话所说的，这题就是个小学奥数题，一个简单的周期问题。最优方案如下表：
|使用的第几个表情|表情编号（从$0$开始，排序后）|
|-|-|
|$1$|$n-1$|
|$2$|$n-1$|
|$......$|$......$|
|$k$|$n-1$|
|$k+1$|$n-2$|
|周期结束分割线|$-----------$|
|$k+2$|$n-1$|
|$k+3$|$n-1$|
|$......$|$......$|
|$2k$|$n-1$|
|$2k+1$|$n-2$|
|周期结束分割线|$-----------$|
|$2k+2$|$n-1$|
|$......$|$......$|
|$m$|$n-1$（如果$m\bmod k=0$，则为$n-2$）|
所以，我们要定义一个变量，统计最后结果：
```cpp
int ans=0;
```
后面要加上好多个数，我就分开写，这样看的更清楚：
```cpp
ans+=m/(k+1)*(a[n-1]*k+a[n-2]);
```
其中，`m/(k+1)`为**完整**周期个数，`a[n-1]*k`为周期中第$1$~$k$个表情快乐值的总和，`a[n-2]`就是周期中第$k+1$个表情的快乐值。
然后处理不完整周期：
```cpp
ans+=m%(k+1)*a[n-1];
```
`m%(k+1)`就是不完整周期数的个数，剩下的应该不用我解释了吧。
最后：
```cpp
printf("%lld",ans);//再次提醒我们这是long long
return 0;
}
```
放上完整代码：
```cpp
#include"stdio.h"
#include"algorithm"
using namespace std;
#define int long long
signed main(void){
int n,m,k,a[200000],cnt=0;
int ans=0;
scanf("%lld%lld%lld",&n,&m,&k);
for(int i=0;i<n;i++)
scanf("%lld",&a[i]);
sort(a,a+n);
ans+=m/(k+1)*(a[n-1]*k+a[n-2])+m%(k+1)*a[n-1];
printf("%lld",ans);
return 0;
}
```
最后说两件事：
第一件事是给管理们说的：**这是蒟蒻的第一篇题解，求过！**
第二件事是给过路的大佬们说的：**这是蒟蒻的第一篇题解，可能会存在不少错误，欢迎大佬来喷！**