题目分析
实质上就是求余数,找到n mod a[i] 的最小值,然后把 i 与 n/a[i] 输出。就是一道纯粹的模拟题,不过因为翻译,要注意隐隐约约有10e18的数据范围,一定要小心,用long long才行(一开始吓得我想用高精(雾))。
主要思路
枚举出每一个 a[i] 然后让 n mod a[i] ,去找最小值。
代码实现
第一种方法:(有点像楼上dalao的)
PS:这个可以被优化为第二种方法
时间复杂度O(k),空间复杂度O(k);
#include<iostream> #include<cstdio> using namespace std; #define ll long long //long long打起来有点费劲(偷懒 #define mn 100010 #define go(i,j,n,k) for(register ll i=j;i<=n;i+=k)//循环偷懒 inline ll read(){//读入优化 ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const ll inf=9223372036854775807;//初始化最小值用的 ll n,k,a[mn],mi,mii;//n 仓鼠的总数 k 笼子种数 //a[]记录所有笼子可装仓鼠的只数 mi 记录最佳的笼子剩余的只数 //mii 记录最佳笼子的编号 int main(){ n=read();k=read(); go(i,1,k,1){ a[i]=read(); }//读入 mi=inf;//初始化最小值(最佳) go(i,1,k,1){ if(n%a[i]<mi){//更新最佳笼子 mii=i; mi=n%a[i]; } } cout<<mii<<" "<<n/a[mii];//输出最佳笼子编号与所需的笼子个数 return 0; }
第二种方法:(简单的优化)
(理论)
时间复杂度:O(k) 空间复杂度:O(1);
重复的就不多讲了,以下主要讲优化
#include<iostream> #include<cstdio> using namespace std; #define ll long long #define mn 100010 #define go(i,j,n,k) for(register ll i=j;i<=n;i+=k) inline ll read(){ ll x=0,f=1;char ch=getchar(); while(ch>'9'||ch<'0'){if(ch=='-')f=-f;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } const ll inf=9223372036854775807; ll n,k,a,m,mi,mii;//a 变为了单个的变量 m 记录当前最佳笼子的a的值 int main(){ n=read();k=read(); mi=inf; go(i,1,k,1){//变为一个循环 a=read();//读入不变 if(n%a<mi){//读入后直接判断 mi=n%a; m=a;//记录下来最佳(否则就会被覆盖掉) mii=i; } } cout<<mii<<" "<<n/m;//n/m则为笼子个数 return 0; }
后记
不知为什么优化后占用内存还会这么多,,,
第二次发题解请大佬多多指教,,,