本题最优解法，时空复杂度均为O(1)。

很明显的分类讨论，在纸上画几个图，不难写出如下代码：

#include <bits/stdc++.h>
using namespace std;
int n;
int main(){
	cin>>n;
	if(n==1){
		cout<<3;
		return 0;
	}
	switch(n%5){
	case 0:
		cout<<n/5;break;
	case 1:
		cout<<(n/5)+1;break;
	case 2:
		cout<<(n/5)+2;break;
	case 3:
		cout<<(n/5)+1;break;
	case 4:
		cout<<(n/5)+4;break;
	}
}

对于 n==1 那个情况调了半天，差点没把我气死。

嗨嗨嗨来发个题解 先写头文件

#include<bits/stdc++.h>
#define maxp 2e5+10
using namespace std;

这道题我用的是记忆化搜索和BFS，那就建一个记忆化数组和一个队列

int p,a[maxp];
queue<int>Q;

下面这个函数来判断数据是否越界以及是否已经搜索过了

bool check(int t){
	if(t>0&&t<=200000&&a[t]==0)
		return 1;
	return 0;
}

接着开始求每个数需要的步数 首先3和5只需要一步，即a[3]=a[5]=1，其他数如果算过了即a[t]!=0就不用重复计算，没算过的等于他前一步的数值加1 比如在其中算到a[12]=4时，此时a[7]=3，a[9]=3，a[15]=3，a[17]=0，向前后走3或5步，a[7]a[9]a[15]都不等于零不用管，a[17]等于零，那么a[17]=a[12]+1

void build(){
	a[3]=a[5]=1;
	Q.push(3);
	Q.push(5);
	while(!Q.empty()){
		int t=Q.front();
		if(check(t+3)){
			a[t+3]=a[t]+1;
			Q.push(t+3);
		}
		if(check(t+5)){
			a[t+5]=a[t]+1;
			Q.push(t+5);
		}
		if(check(t-3)){
			a[t-3]=a[t]+1;
			Q.push(t-3);
		}
		if(check(t-5)){
			a[t-5]=a[t]+1;
			Q.push(t-5);
		}
		Q.pop();
	}
	return;
}

此时所有数需要的步数都有了直接提出来就行了

int main()
{
	build();
	cin>>p;
	cout<<a[p]<<"\n";
	return 0;
}

你们最喜欢的完整代码来啦

#include<bits/stdc++.h>
#define maxp 2e5+10
using namespace std;
int p;
int a[maxp];
queue<int>Q;
bool check(int t){
	if(t>0&&t<=200000&&a[t]==0)
		return 1;
	return 0;
}
void build(){
	a[3]=a[5]=1;
	Q.push(3);
	Q.push(5);
	while(!Q.empty()){
		int t=Q.front();
		if(check(t+3)){
			a[t+3]=a[t]+1;
			Q.push(t+3);
		}
		if(check(t+5)){
			a[t+5]=a[t]+1;
			Q.push(t+5);
		}
		if(check(t-3)){
			a[t-3]=a[t]+1;
			Q.push(t-3);
		}
		if(check(t-5)){
			a[t-5]=a[t]+1;
			Q.push(t-5);
		}
		Q.pop();
	}
	return;
}
int main()
{
	build();
	cin>>p;
	cout<<a[p]<<****"\n";
	return 0;
}

完结撒花 QwQ~~~

#include<bits/stdc++.h> using namespace std; int main() { long long n,m,t,v=20000; cin>>n; for(m=0;m<=13555;m++) { for(t=0;t<=13555;t++) { if(n3m+5t||n3m-5t||n==5t-3m) { v=min(m+t,v); } } } cout<<v; return 0; }

就那样

#include<bits\stdc++.h>
using namespace std;
int p,s;
int main(){
cin>>p;
while(p){
if(p>=5&&p%3){p-=5;s++;
}else if(p>=3){
p-=3;s++;
}else if(p==2){
s+=2;
break;
}else if(p==1){
s+=3;
break;
}
}
cout<<s<<endl;
return 0;
}

#include<bits/stdc++.h> using namespace std; int x[3]; int main() { int a,b=0; cin>>a; while(a) { if(a>=5&&a%3!=0) { a-=5; b++; } else if(a>=3) { a-=3; b++; } else if(a2) { b+=2; break; } else if(a1) { b+=3; break; } } cout<<b; }

#include<bits/stdc++.h>
using namespace std;
int p,minn=66666;
int main(){
	cin>>p;
	for(int x=0;x<=20000;++x){
		for(int y=0;y<=25000;++y){
			if(3*x-5*y==p||5*y-3*x==p||3*x+5*y==p){
				minn=min(x+y,minn);
			}
		}
	}
	cout<<minn<<endl;
	return 0;
}

不是最优的方法，但勉强能过。