题解 CF1117B 【Emotes】

· · 题解

这是一道比较水（你看这题难度不就是水的颜色吗）的小学奥数题（考察知识点：周期问题）。。。

此题解在题解区域食用更佳（原因：我那个表格在博客里貌似显示不出来）

首先搭上框架：

#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）

所以，我们要定义一个变量，统计最后结果：

    int ans=0;

后面要加上好多个数，我就分开写，这样看的更清楚：

    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个表情的快乐值。

然后处理不完整周期：

    ans+=m%(k+1)*a[n-1];

m%(k+1)就是不完整周期数的个数，剩下的应该不用我解释了吧。

最后：

    printf("%lld",ans);//再次提醒我们这是long long
    return 0;
}

放上完整代码：

#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;
}

最后说两件事：

第一件事是给管理们说的：这是蒟蒻的第一篇题解，求过！

第二件事是给过路的大佬们说的：这是蒟蒻的第一篇题解，可能会存在不少错误，欢迎大佬来喷！