64,656
社区成员
发帖
与我相关
我的任务
分享算法问题：唱片问题（求高手赐教，详细的C++代码）
算法问题：唱片问题（求高手赐教，详细的C++代码）
★问题描述：
现在有n首歌，每首歌的长度都是m秒，而一块唱片共可存储s秒长度的音乐。但在存音乐的过程中，我们要求两首歌之间有1秒的间隔。而且存歌的人很迷信，一张唱片存的歌曲数不得为13的倍数。
★实验任务：
现在给你n、m和s，请求出最少需要几张唱片才能存储所有歌曲。
★数据输入：
输入数据第一行包含三个整数n(1≤n≤100)、m(1≤m≤s)以及s(1≤s≤10000)。
★结果输出：
输出一行一个整数，即最少所需唱片的张数。
输入示例 输出示例
26 1 100 2
求详细C++代码。
★问题描述：
现在有n首歌，每首歌的长度都是m秒，而一块唱片共可存储s秒长度的音乐。但在存音乐的过程中，我们要求两首歌之间有1秒的间隔。而且存歌的人很迷信，一张唱片存的歌曲数不得为13的倍数。
★实验任务：
现在给你n、m和s，请求出最少需要几张唱片才能存储所有歌曲。
★数据输入：
输入数据第一行包含三个整数n(1≤n≤100)、m(1≤m≤s)以及s(1≤s≤10000)。
★结果输出：
输出一行一个整数，即最少所需唱片的张数。
输入示例 输出示例
26 1 100 2
求详细C++代码。
...全文
请发表友善的回复…
发表回复
方寸之间 2011-06-18
- 打赏
- 举报
再更新，最终版：
int GetMinDiscCount(int n, int m, int s)
{
const int distTime = 1; // 间隔时间 1s
int musicPerDisc = (s+distTime)/(m+distTime); // 每张盘放的歌的数量
if(musicPerDisc % 13 == 0) // 对于13的迷信问题处理
--musicPerDisc;
int discCount = n/musicPerDisc; // 唱片数量
int otherMusic = n - musicPerDisc * discCount; // 当前唱片数量下剩余的music数量，这些已不足一张唱片了
if(otherMusic != 0) // 增加剩余music数量不为0的处理
{
/* 经测试，只有一种情形比较特殊：当剩余数量是13的倍数，且与其他盘数量相差为1或无盘分配时，需要扩充2个盘
* 如用例：53 2 80 */
if(otherMusic % 13 == 0 && (discCount == 0 || musicPerDisc - otherMusic == 1))
discCount += 2;
else
++discCount;
}
return discCount;
}
方寸之间 2011-06-17
- 打赏
- 举报
新的测试用例：
26 1 100 -> 2
27 605 2528 -> 7
46 697 1051 -> 46
53 3349 7512 -> 27
71 2734 7496 -> 36
57 938 2018 -> 29
83 431 2673 -> 14
51 1723 2628 -> 51
48 1924 2090 -> 48
8 3543 4167 -> 8
4 3564 3783 -> 4
34 6354 8838 -> 34
3 834 9808 -> 1
46 4593 7037 -> 46
41 847 1141 -> 41
27 5127 8898 -> 27
23 161 6208 -> 1
22 704 1235 -> 22
2 814 1024 -> 2
71 4197 5621 -> 71
57 345 970 -> 29
70 958 3276 -> 24
41 3099 7926 -> 21
10 502 2132 -> 3
11 1014 1541 -> 11
92 2567 9284 -> 31
5 5621 5916 -> 5
1 208 244 -> 1
99 1533 1661 -> 99
67 5836 9507 -> 67
66 1086 1143 -> 66
请按任意键继续. . .
26 1 100 -> 2
27 605 2528 -> 7
46 697 1051 -> 46
53 3349 7512 -> 27
71 2734 7496 -> 36
57 938 2018 -> 29
83 431 2673 -> 14
51 1723 2628 -> 51
48 1924 2090 -> 48
8 3543 4167 -> 8
4 3564 3783 -> 4
34 6354 8838 -> 34
3 834 9808 -> 1
46 4593 7037 -> 46
41 847 1141 -> 41
27 5127 8898 -> 27
23 161 6208 -> 1
22 704 1235 -> 22
2 814 1024 -> 2
71 4197 5621 -> 71
57 345 970 -> 29
70 958 3276 -> 24
41 3099 7926 -> 21
10 502 2132 -> 3
11 1014 1541 -> 11
92 2567 9284 -> 31
5 5621 5916 -> 5
1 208 244 -> 1
99 1533 1661 -> 99
67 5836 9507 -> 67
66 1086 1143 -> 66
请按任意键继续. . .
方寸之间 2011-06-17
- 打赏
- 举报
更正一下：少处理一步。
int GetMinDiscCount(int n, int m, int s)
{
const int distTime = 1; // 间隔时间 1s
int musicPerDisc = (s+distTime)/(m+distTime); // 每张盘放的歌的数量
if(musicPerDisc % 13 == 0) // 对于13的迷信问题处理
--musicPerDisc;
int discCount = n/musicPerDisc; // 唱片数量
int otherMusic = n - musicPerDisc * discCount; // 当前唱片数量下剩余的music数量，这些已不足一张唱片了
if(otherMusic != 0) // 增加剩余music数量不为0的处理
{
if(otherMusic % 13 == 0) // 要注意剩余的唱片数量是否是13的倍数
discCount += 2;
else
++discCount;
}
return discCount;
}
#include <time.h>
int _tmain(int argc, _TCHAR* argv[])
{
printf("%d\t %d\t %d\t -> %d\n", 26, 1, 100, GetMinDiscCount(26, 1, 100));
srand((unsigned int)time(NULL));
for(int i = 0; i < 30; i++)
{
int n = rand()%100 + 1;
int s = rand()%10000 + 1;
int m = rand()%s + 1;
printf("%d\t %d\t %d\t -> %d\n", n, m, s, GetMinDiscCount(n, m, s));
}
system("pause");
return 0;
}
方寸之间 2011-06-17
- 打赏
- 举报
看了一下，发现都不太对。我也贴一个O(1)的
测试用例：
26 1 100 -> 2
80 521 882 -> 82
8 2417 4601 -> 10
79 107 1095 -> 8
57 3596 9266 -> 29
86 7010 9093 -> 88
74 2061 5690 -> 39
40 16 98 -> 10
64 37 1055 -> 3
93 948 4625 -> 24
78 4857 6691 -> 80
28 660 2667 -> 9
1 3033 5650 -> 3
25 1516 4972 -> 9
54 3945 4143 -> 56
76 399 8263 -> 4
8 3996 8495 -> 6
39 91 139 -> 41
63 6875 8840 -> 65
27 4061 9889 -> 14
24 274 842 -> 10
51 965 1164 -> 53
90 2292 5268 -> 47
20 508 4915 -> 3
11 5934 6093 -> 13
24 695 5061 -> 4
81 150 223 -> 83
94 1315 2787 -> 49
13 1004 7883 -> 2
52 328 5036 -> 4
35 27 3241 -> 1
请按任意键继续. . .
int GetMinDiscCount(int n, int m, int s)
{
const int distTime = 1; // 间隔时间 1s
int musicPerDisc = (s+distTime)/(m+distTime); // 每张盘放的歌的数量
if(musicPerDisc % 13 == 0) // 对于13的迷信问题处理
--musicPerDisc;
int discCount = n/musicPerDisc; // 唱片数量
int otherMusic = n - musicPerDisc * discCount; // 当前唱片数量下剩余的music数量，这些已不足一张唱片了
if(otherMusic % 13 == 0) // 要注意剩余的唱片数量是否是13的倍数
discCount += 2;
else
++discCount;
return discCount;
}
#include <time.h>
int _tmain(int argc, _TCHAR* argv[])
{
printf("%d\t %d\t %d\t -> %d\n", 26, 1, 100, GetMinDiscCount(26, 1, 100));
srand((unsigned int)time(NULL));
for(int i = 0; i < 30; i++)
{
int n = rand()%100 + 1;
int s = rand()%10000 + 1;
int m = rand()%s + 1;
printf("%d\t %d\t %d\t -> %d\n", n, m, s, GetMinDiscCount(n, m, s));
}
system("pause");
return 0;
}
测试用例：
26 1 100 -> 2
80 521 882 -> 82
8 2417 4601 -> 10
79 107 1095 -> 8
57 3596 9266 -> 29
86 7010 9093 -> 88
74 2061 5690 -> 39
40 16 98 -> 10
64 37 1055 -> 3
93 948 4625 -> 24
78 4857 6691 -> 80
28 660 2667 -> 9
1 3033 5650 -> 3
25 1516 4972 -> 9
54 3945 4143 -> 56
76 399 8263 -> 4
8 3996 8495 -> 6
39 91 139 -> 41
63 6875 8840 -> 65
27 4061 9889 -> 14
24 274 842 -> 10
51 965 1164 -> 53
90 2292 5268 -> 47
20 508 4915 -> 3
11 5934 6093 -> 13
24 695 5061 -> 4
81 150 223 -> 83
94 1315 2787 -> 49
13 1004 7883 -> 2
52 328 5036 -> 4
35 27 3241 -> 1
请按任意键继续. . .
zhy905692718 2011-06-17
- 打赏
- 举报
#include<iostream.h>
int CDnum(int m, int n, int s);
int main()
{
int m=1, n=2, s=3, iCDnum;
cout<<"请输入歌曲数量n、每首歌的长度m、以及每张唱片的容量s："<<endl;
cin>>n>>m>>s;
iCDnum=CDnum(m, n, s);
if(iCDnum!=0)
{
cout<<"唱片数："<<iCDnum<<endl;
}
else
{
cout<<"Error!!!";
}
return 0;
}
int CDnum(int m, int n, int s)
{
if((m<=s&&m>0)&&(n<=100&&n>0)&&(s<=10000&&s>0))
{
int iCDnum, iSongnum;
int im=m+1, is=s+1; //解决每两首歌之间的间隙和最后一首没有的问题！
iSongnum=is/im;
if(iSongnum%13==0)
iSongnum--;
iCDnum=n/iSongnum;
if(n%iSongnum!=0)
iCDnum++;
return iCDnum;
}
else
{
return 0;
}
}
这个是C++6.0下的，运行过没问题！！！
int CDnum(int m, int n, int s);
int main()
{
int m=1, n=2, s=3, iCDnum;
cout<<"请输入歌曲数量n、每首歌的长度m、以及每张唱片的容量s："<<endl;
cin>>n>>m>>s;
iCDnum=CDnum(m, n, s);
if(iCDnum!=0)
{
cout<<"唱片数："<<iCDnum<<endl;
}
else
{
cout<<"Error!!!";
}
return 0;
}
int CDnum(int m, int n, int s)
{
if((m<=s&&m>0)&&(n<=100&&n>0)&&(s<=10000&&s>0))
{
int iCDnum, iSongnum;
int im=m+1, is=s+1; //解决每两首歌之间的间隙和最后一首没有的问题！
iSongnum=is/im;
if(iSongnum%13==0)
iSongnum--;
iCDnum=n/iSongnum;
if(n%iSongnum!=0)
iCDnum++;
return iCDnum;
}
else
{
return 0;
}
}
这个是C++6.0下的，运行过没问题！！！
linji7602931 2011-06-17
- 打赏
- 举报
主要是不会，一张唱片存的歌曲数不得为13的倍数。这个的处理方法。
wangziwo0 2011-06-17
- 打赏
- 举报
谢谢你的补充
linji7602931 2011-06-17
- 打赏
- 举报
忘记说了，是在V C++ 6.0 环境下的。
dingdangmimi 2011-06-17
- 打赏
- 举报
人工置顶下，给点思路呀。
gz_qmc 2011-06-17
- 打赏
- 举报
// n-歌曲数目
// m-歌曲长度
// S-光盘容量
// t-时间间隔
int GetNumber(int n,int m,int s,int t)
{
int count;
int nn=n+1;
int mm=m;
int i=1;
count=n>0;
while(i<nn)
{
if(i%13==0)
{
nn++;
count++;
mm=m;
continue;
}
if(mm>s)
{
count++;
mm=m;
continue;
}
mm+=m+t;
}
return count;
}
//应用举例
void main()
{
int pNum=GetNumber(64,180,900,1);
}
gz_qmc 2011-06-17
- 打赏
- 举报
// n-歌曲数目
// m-歌曲长度
// S-光盘容量
// t-时间间隔
int GetNumber(int n,int m,int s,int t)
{
int count=0;
int nn=n+1;
int mm=m;
int i=1;
while(i<nn)
{
if(i%13==0)
{
nn++;
count++;
mm=m;
continue;
}
if(mm>s)
{
count++;
mm=m;
continue;
}
mm+=m+t;
}
}
//应用举例
void main()
{
int pNum=GetNumber(64,180,900,1);
}
qq120848369 2011-06-17
- 打赏
- 举报
#include <iostream>
using namespace std;
/*
现在有n首歌，每首歌的长度都是m秒，而一块唱片共可存储s秒长度的音乐。
但在存音乐的过程中，我们要求两首歌之间有1秒的间隔。而且存歌的人很迷信，一张唱片存的歌曲数不得为13的倍数。
*/
int m,n,s;
int getOnePiece()
{
int cnt=s/m,space=s%m;
if(space>=cnt-1) //there are enough secs to seperate each song
{
if(cnt%13==0)
{
return cnt-1;
}
else
{
return cnt;
}
}
for(cnt=cnt-1,space=space+m;cnt>=1;--cnt,space=space+m)
{
if(space>=cnt-1)
{
if(cnt%13==0)
{
return cnt-1;
}
else
{
return cnt;
}
}
}
return cnt; //cnt==0
}
int main()
{
cin>>n>>m>>s;
int cnt=getOnePiece();
if(n%cnt==0)
{
cout<<n/cnt<<endl;
}
else
{
cout<<(n/cnt)+1<<endl;
}
return 0;
}
明明一张盘就够了...
gz_qmc 2011-06-17
- 打赏
- 举报
错了,修改一下
/ n-歌曲数目
// m-歌曲长度
// S-光盘容量
// t-时间间隔
int GetNumber(int n,int m,int s,int t)
{
int count;
int nn=n+1;
int mm=m;
int i=1;
count=n>0;
for(int i=0;i<nn;i++)
{
/*如果是13的倍数首并且多装一首都不够,或者当前这首就不够,那么要换新碟了
if(((i%13==0)&&(mm+m+t)>s)||mm>s)
{
count++;
mm=m;
}
else mm+=m+t;
i++;
}
return count;
}
//应用举例
void main()
{
int pNum=GetNumber(64,180,900,1);
}
zhy905692718 2011-06-17
- 打赏
- 举报
不好意思，不常贴代码，这贴上去还没缩进了！
zhy905692718 2011-06-17
- 打赏
- 举报
lz的例子是不有点小问题！
#include<iostream>
using namespace std;
int CDnum(int m, int n, int s);
int main()
{
int m=1, n=2, s=3, iCDnum;
cout<<"请输入歌曲数量n、每首歌的长度m、以及每张唱片的容量s："<<endl;
cin>>n>>m>>s;
iCDnum=CDnum(m, n, s);
if(iCDnum!=0)
{
cout<<"唱片数："<<iCDnum<<endl;
}
else
{
cout<<"Error!!!";
}
return 0;
}
int CDnum(int m, int n, int s)
{
if((m<=s&&m>0)&&(n<=100&&n>0)&&(s<=10000&&s>0))
{
int iCDnum, iSongnum;
int im=m+1, is=s+1; //解决每两首歌之间的间隙和最后一首没有的问题！
iSongnum=is/im;
if(iSongnum%13==0)
iSongnum--;
iCDnum=n/iSongnum;
if(n%iSongnum!=0)
iCDnum++;
return iCDnum;
}
else
{
return 0;
}
}
希望能有用！
#include<iostream>
using namespace std;
int CDnum(int m, int n, int s);
int main()
{
int m=1, n=2, s=3, iCDnum;
cout<<"请输入歌曲数量n、每首歌的长度m、以及每张唱片的容量s："<<endl;
cin>>n>>m>>s;
iCDnum=CDnum(m, n, s);
if(iCDnum!=0)
{
cout<<"唱片数："<<iCDnum<<endl;
}
else
{
cout<<"Error!!!";
}
return 0;
}
int CDnum(int m, int n, int s)
{
if((m<=s&&m>0)&&(n<=100&&n>0)&&(s<=10000&&s>0))
{
int iCDnum, iSongnum;
int im=m+1, is=s+1; //解决每两首歌之间的间隙和最后一首没有的问题！
iSongnum=is/im;
if(iSongnum%13==0)
iSongnum--;
iCDnum=n/iSongnum;
if(n%iSongnum!=0)
iCDnum++;
return iCDnum;
}
else
{
return 0;
}
}
希望能有用！
