题解 CF439A 【Devu, the Singer and Churu, the Joker】

· · 题解

我们先要找出最优解的规律：

样例的解释给了蒟蒻我很大的帮助，通过解释（那里的英文应该是比较好理解的），可以发现每次当Devu休息时，Churu都可以讲两个笑话，唱歌休息期间能讲(n-1)×2个笑话。

另外一开始需要特判Devu是否能在规定时间内唱完所有的歌，如果不可以的话，就直接 输出1+return 0 。

还有一种情况一些同学们容易忘掉，那就是如果Devu唱完歌后还有很多时间，那么Churu则应该继续讲笑话，那么需要一个变量sum记录一下Devu的唱歌总时长，它的大小是：(a[1]+a[2]+a[3]+...+a[n])+(n-1)×10，所以Churu在剩下时间能讲的笑话总数是sum/5。

思路讲完，代码写出：

#include<cstdio>//头文件
using namespace std;
int n,d;//歌的总数和总时间
int a[110];//记录每首歌时间的数组，数据范围是100
int sum;//唱歌总时间
int ans;//答案变量
int main(){
    scanf("%d%d",&n,&d);//输入
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);//循环输入每首歌的长度
        sum+=a[i];//在输入时顺便把sum中歌唱总时间记录
    }
    sum+=((n-1)*10);//两首歌之间的休息时间也算上
    if(sum>d)//特判是否能唱完所有歌
    {
        printf("-1\n");//如果不能，输出-1
        return 0;//结束程序
    }
    ans+=((n-1)*2);//休息期间的笑话总数
    ans+=((d-sum)/5);//唱完歌后的笑话总数，经过了上面的特判，肯定是非负数
    printf("%d\n",ans);//输出答案（养成结尾换行的好习惯）
    return 0;//结束程序
}

然后就能AC了。

下次题解见，Bye~