上海计算机学会2021年2月月赛C++丙组T4切香肠
发布时间
阅读量：
阅读量
题目描述
共有n根长度一致的香肠, 我们计划将其均匀地分配给k位客人. 为此, 我们准备将这些香肠切开, 并确保每位客人的分配量相同. 同时, 我们会严格遵循公平原则, 不进行任何剩余.
为了完成任务，请问最少需要切多少刀？每刀仅限于切断一条香肠。每位客人最多可以接受多段香肠。
输入格式
两个整数：n 与 k。
输出格式
单个整数：表示最少需要切几刀。
数据范围
- 对于 40%的数据，1≤n,k≤50；
- 对于 70%的数据，1≤n,k≤5000；
- 对于 100%的数据，1≤n,k≤5,000,000。
- 对于附加数据，1≤n,k≤10^15。
样例数据
试算结果如下：
当n=2时（即n=2），计算得出m=6个单位长度；当n=6时（即n=6），计算得出m=4个单位长度；当n=5时（即n=5），计算得出m=10个单位长度
解析：
第一种方式：纯模拟
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k;
int ans=0;
cin >> n >> k;
if (n % k == 0) {//能整分
cout << 0 << endl;
} else {//不能整分
long long sum=0;
//每个人分到n/k的香肠
for (int i=1;i<=k;i++){
sum+=n;//分到第i个人的时候的分子
if (sum%k!=0){//如果不能整除，需要切一刀
ans++;
}
}
cout<<ans;
}
return 0;
}第二种方法：
先去掉能整个分的香肠，留下不能整分的；
当无法均等分割时（即香肠数量与人数的最大公约数不为零），计算香肠数量与人数的最大公约数，并按此数值划分成若干组。这样做的结果是：每一组都会获得完整数量的香肠。
然后每组切人数减1刀即可。
详见代码：
#include <bits/stdc++.h>
using namespace std;
int gcd(int x,int y){//求最大公约数
while(y!=0){
int tmp=x%y;
x=y;
y=tmp;
}
return x;
}
int main() {
int n, k;
cin >> n >> k;
n = n % k;//先把整个的分掉，留下不能整分的
if (n == 0) {//分完，不用切
cout << 0 << endl;
} else {//分不完的情况
int a = gcd(n,k);//求最大公约数
//k个人分成a组，每组都会对应整根的香肠
//每组都刀数等于人数减1
//乘以a组，就是总刀数
cout << (k / a - 1)*a << endl;
}
return 0;
}更简洁的写法：
#include <bits/stdc++.h>
using namespace std;
long long n,k;
long long ans=0;
long long gcd(long long x,long long y){
if (x%y==0) return y;
return gcd(y,x%y);
}
int main() {
cin >> n >> k;
cout<<k-k/(k/gcd(n,k));
return 0;
}全部评论 (0)
还没有任何评论哟~