【头条笔试】出专辑

你作为一名出道的歌手终于要出自己的第一份专辑了，你计划收录 n 首歌而且每首歌的长度都是 s 秒，每首歌必须完整地收录于一张 CD 当中。每张 CD 的容量长度都是 L 秒，而且你至少得保证同一张 CD 内相邻两首歌中间至少要隔 1 秒。为了辟邪，你决定任意一张 CD 内的歌数不能被 13 这个数字整除，那么请问你出这张专辑至少需要多少张 CD ？

输入描述:

每组测试用例仅包含一组数据，每组数据第一行为三个正整数 n, s, L。 保证 n ≤ 100 , s ≤ L ≤ 10000

输出描述:

输出一个整数代表你至少需要的 CD 数量。

输入例子:

7 2 6

输出例子:

4

算法思想

动态规划。

1、一张CD放得下时

检查n是否为13的倍数，如果是则多加一张CD

2、多张CD存放时

如果剩下的放在最后一张的歌曲数是13的倍数，那么可以倒数第二张少放1，最后一张加1，这样就不用多加CD了

但是考虑到，如果倒数第二张的歌曲数（为每张CD能存放的歌曲数）只比最后一张数目多1，那么就不能从倒数第二张拿了。

举个例子：

后三张为14 14 13，就不能重排为14 13 14（因为又把倒数第二张变成了13）

而大家可能会问，那就从倒数第二张拿2个啊。

此时，后三张变成14 12 15，貌似可以，但是！ 15超了每张CD的最大存放数！！因为最后一张只比倒数第二张数目（最大存放数）少1啊！！

AC代码如下：

#include <iostream> using namespace std; int main() { int n,s,l; while( cin>>n>>s>>l ){ int num_eachCD = (l+1)/(s+1); if( num_eachCD==0 ) --num_eachCD; int num_CD = n/num_eachCD; if( n%num_eachCD>0 ) ++num_CD; if( num_CD==1 ){//一张CD放得下 if( n==0 ) ++num_CD; } else{//需多张CD if( (n%num_eachCD)==0 && num_eachCD-1==n%num_eachCD )//注意此处！ ++num_CD; } cout<<num_CD<<endl; } return 0; }