今天比赛我像一个智障一样,这个题都没满分
算法1
(暴力枚举) $O(n)$
直接就枚举女生分到的宿舍O(n)复杂度,可以过。
不知道我比赛时在想什么
时间复杂度
参考文献
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e5+10;
int n0,n1,n;
int ans1=0,ans2=1e5+1;
int min1 = inf;
int main()
{
scanf("%d%d%d",&n0,&n1,&n);
int flog=0;
if(n0==0){
if(n1%n==0) printf("%d %d\n",0,n);
else printf("No Solution\n");
return 0;
}
if(n1==0){
if(n0%n==0) printf("%d %d\n",n,0);
else printf("No Solution\n");
return 0;
}
//枚举女生分到的宿舍假定是i
for(int i=1;i<n;i++){
if(n0%i==0&&n1%(n-i)==0&&n0>i&&n1>(n-1)){
flog=1;
int num = abs(n0/i-n1/(n-i));
if(num<min1){
ans1=i;
ans2=n-i;
min1=num;
}
}
}
if(flog==0) printf("No Solution\n");
else printf("%d %d\n",ans1,ans2);
return 0;
}