题目描述
题目描述很简单，一共 \(n\) 瓶饮料，每 \(3\) 瓶饮料的瓶盖可以再换 \(1\) 瓶新的饮料，问最后一共喝了几瓶饮料？
题意分析
此题一共有 \(3\) 种做法，接下来我们一个一个分析：
\(1.\)
第一种也是最简单的一种，首先我们定义两个变量
long long n;//为初始瓶数
long long p;//为瓶盖数
由于 \(n\) 个瓶子有 \(n\) 个瓶盖，所以我们要把 \(p\) 初始的值改为 \(n\)。
接下来模拟即可
AC 代码
#include<bits/stdc++.h>
using namespace std;
long long n,p;
int main(){
cin>>n;
p=n;
while(n>=3){
n-=3;
n++;
p++;
}
cout<<p<<endl;
}
\(2.\)
第二种方法就是不停做除法，在考虑余数的情况下，我们拿 \(n=100\) 这一组数来举例：
\(100\to33\to11+1\to4\to1+1\)
最后的 \(100+33+11+4+1=149\) 就是最后结果
所以对于一个数 \(n\) 有三种情况：
\((1)\) \(n\) \(%\) \(3=0\)
\((2)\) \(n\) \(%\) \(3=1\)
\((3)\) \(n\) \(%\) \(3=2\)
对于这三种情况，我们分别处理：
当 \(n\) \(%\) \(3=x\) 时，我们做完第一步运算再在后面加上 \(x\) 即可。
AC 代码
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
long long n,sum=0,p;
int main() {
cin>>n;
sum=n;
while(n){
if(n%3==0){
if(n<3) break;
p=n/3;
sum+=p;
n/=3;
}
else if(n%3==1){
if(n<3) break;
p=(n-1)/3;
sum+=p;
n-=1;
n/=3;
n+=1;
}
else if(n%3==2){
if(n<3) break;
p=(n-2)/3;
sum+=p;
n-=2;
n/=3;
n+=2;
}
}
cout<<sum<<endl;
return 0;
}
\(3.\)
第 \(3\) 种方法也是最难的一种，我们可以在 \(\Theta(1)\) 的时间复杂度中推出数学公式解决这道题。
数学公式如下：
n+(n-1)/2
那这个公式是怎么出来的呢？
首先，我们知道，\(n\) 每减少 \(3\) 就会增加 \(1\)，所以式子我们可以写成：
n+n/2
我们发现，\(n\) 对 \(2\) 只有两种余数，而这个余数决定了 \(n\) 的奇偶性。
当我们手推一遍 \(n=15\) 和 \(n=16\) 时的值时，变化如下：
\(15\to13\to11\to9\to7\to5\to3\to1\) //一共额外得到7瓶
\(16\to14\to12\to10\to8\to6\to4\to2\) //一共也是7瓶
但是当我们运行此代码时，发现代码中 \(16\) 的额外得到的值为 \(8\)。
原因就是因为 \(n=16\) 时最后一次兑换的瓶盖数为 \(2\)，明明已经不能兑换了，但由于n/2的缘故，最后的结果多算了一瓶。
所以我们想到的方法是让 \(n\) 减去 \(1\) 这样既不会多算，也不会少算。
AC 代码
#include<bits/stdc++.h>
using namespace std;
long long n,p;
int main(){
cin>>n;
p=n+(n-1)/2;
cout<<p<<endl;
}