本人第一篇题解，求过

【目录】

1.目录

2.题外话

3.大意

4.思路

5.扩展

6.代码

7.彩蛋

8.广告

【题外话】

这题目有问题，跟三遣救援有关系吗？

【题目大意】

有n瓶药，其中有一个多了几片药，给你一个载重量为m的天平，问几次能找出这瓶多一点的药？

【思路】

先不考虑m

我们假设每组k只猪，那么前两组k+1只，最后一组k只，为最优解

递推式：f(n)=f(n/3)+1;

再说m的影响

我们发现，只有n>=m*3+2这种情况会产生影响，那此时递推式就是f(n)=f(n-2m)+1

我话没有说完，x=1时，不用称！

总结一下，就是如下

     0  n=1
     /
    /
f(n)--f(n/3)+1 3m+2>n>0
    \
     \
     f(n-2m)+1 n>=3m+2

【扩展】

忽略m的情况

这就成了我们熟悉的小学奥数

给大家一个表格，顺便复习一下这个知识

【代码】

我知道你们是来看这个的

不加头文件，防抄袭

int n,m,a[10005];
cin>>n>>m;
for(int i=1;i<=n;i++)
    if(i==1) a[i]=0;
   else if(i>1 && i<3*m+2) a[i]=a[i/3]+1;
   else a[i]=a[i-2*m]+1;

【彩蛋】

P5734 测试点

输入

5
ILove
1 Luogu
2 5 5
3 3 guGugu
4 gu
4 fafa

输出

ILoveLuogu
Luogu
LuoguGugugu
3
-1

【广告】

我的博客：https://252401.blog.luogu.org/

有问题私信我