小苹果OJ链接：http://1.14.20.80/problem.php?id=1682
题意
从左到右依次给n个苹果编号，分别是1，2，...，n；从最左边开始拿苹果，每次拿一个，跳过两个，继续拿，即第一次拿走图片，然后将剩余的苹果从左到右按照1, 2, 3,...排序，问拿走所有苹果需要多少次，且编号为n的苹果是被第几次拿走的。
题目解析
本题数据范围n<=10e9, 因此肯定不能用暴力O(n)复杂度，因为会超时，所以思考一种数学方法。
将苹果从左到右每3个为一组依次进行划分，划分结束后，假设剩余苹果为x个，则mod有3种可能情况：
情况1: x为0 即现有苹果个数刚好为3的倍数，那么此次取走的苹果数量为n/3（每3个一组，一组取一个，共n/3个）；
情况2: x为1 即现有苹果3个一组，划分完后，还剩1个苹果，那么此次取走的苹果数量为n/3+1，剩余的最后一个苹果在本次就会被取走，哎等等，那我们想知道最后一个苹果（即编号为n的苹果）什么时候被拿走，不就是第一次出现x为1的情况下嘛。
情况3: x为2 即现有苹果3个一组，划分完后，还剩2个苹果，那么此次取走的苹果数量为依然是n/3+1；
有了上面三种情况，我们就可以不停更新剩余的苹果数量，直到为0即可，在更新过程中，也要找出第一次出现上面的【情况2】，即为第n个苹果拿走的时间。
参考代码
参考1
#include<bits/stdc++.h>
using namespace std;
// idx记录第n个苹果是第几次拿走的
// sum记录拿走n个苹果共需要几次；
int n, idx = -1, sum = 0;
int main() {
cin >> n;
while(n) { // 当n>0时
sum++; // 由于n>0，所以次数+1
if(idx == -1 && n%3 == 1) idx = sum; // 第一次出现【情况2】记录为拿走第n个苹果的次数
if(n%3 == 0) n = n - n/3; // 【情况1】
else n = n - n/3 - 1; // 【情况2】和【情况3】
}
cout << sum << " " << idx << endl;
return 0;
}
参考2
#include<bits/stdc++.h>
using namespace std;
int n,cnt,ans;
int main() {
cin>>n;
while(n>0){
cnt++;
if(ans==0&&n%3==1)ans=cnt;
n-=(n+2)/3;
}
cout<<cnt<<" "<<ans;
return 0;
}
参考3
#include<bits/stdc++.h>
using namespace std;
int main() {
int n = 0;
cin >> n;
int days = 0;
int lastDay = 0;
bool flag = false;
// n = 3p + r;
while (n > 0 ) {
int p = n / 3;
int r = n % 3;
if (p > 0) {
if (r > 0) {
// 每个组拿一个，余数组拿一个
n -= p + 1;
if (!flag && r == 1) {
lastDay = days + 1;
flag = true;
}
} else {
// 每个组拿一个
n -= p;
}
} else {
// 余数组一个一个拿
n -= 1;
}
days++;
if (!flag) {
lastDay = days;
}
}
cout << days << ' ' << lastDay;
return 0;
}
总结
解决本题需要的编程知识较少，会使用 while 循环，会计数即可。本题的难点在于初等数论的知识，也就是 “任何一个整数，可以表示为被三整除的部分加上余数部分”： n = 3*p + r 理解了这一点，此题也就应刃而解了。