题目传送门

一些往事

去年在写这题时，几乎花了一小时才想出规律…………

题目说明

每天在拿的时候，小苞都是从左侧第 1 个苹果开始、每隔 2 个苹果拿走 1 个苹果。

这说得很清楚了，如果还是不懂，我再翻译一下： 对于 n 个数，每次将 i%3==1 的第 i 个数拿走，并更新 n。

这本能用队列，但因为题目限制：

多少天能拿完所有的苹果，而编号为 nn 的苹果是在第几天被拿走的？

导致很难用队列处理。 先试试暴力。

暴力代码

#include <bits/stdc++.h>
using namespace std;
int n,day;
bool a[1000000005], // 桶，用来存某个数字是否被拿过，0为还没，1为拿了
     f; // 判断第 n 个数字是否被拿
int main(){
    cin >> n;
    for(int i=1;i;i++){ // 用 i 记录天数
        int ans=0; // 记录在第 i 天的数字数
        bool flag=0; // 判断数字是否被拿光
        for(int j=1;j<=n;j++){
            if(!a[j]) flag=1,ans++;
            if(ans%3==1){
                a[j]=1;
                if(j==n&&!f) f=1,day=i;
            }
        }
        if(!flag){
            /* 因为多运行了1次来判断数字是否被拿光，
               所以输出第 1 项时要减 1   */
            cout << i-1 << " " << day;
            return 0;
        }
    }
    return 0;
}

不出意料地拿了90pts。 观察代码，发现我们为了维护操作，开了一个桶，为了省空间，还用 bool 类型。但由于 n 达到了 10⁹ ，导致该程序的时空复杂度变得很大，不懂的可以看下小林老师的算法的空间与时间估算 。

规律分析

先对样例进行模拟

1 2 3 4 5 6 7 8

每一轮后

2 3 5 6 8 3 5 8 5 8 8 空

每次结束后，n 都会比原来少 1/3，但如果 n 不整除 3，还要多减 1，这样就解决了第一问。至于第二问，只要在第 n 位为 n%3==1 时，把当天天数储存就行了。

Code

#include <bits/stdc++.h>
using namespace std;
int n,
    sum, // 总天数
    day, // 第 n 个数被拿走的天数
    flag;// 判断第 n 个数是否被拿
int main(){
    cin >> n;
    while(n!=0){
        sum++; // 新一天
        // 判断第 n 个数是否能拿
        if(n%3==1&&!flag) flag=1,day=sum;
        // 减数操作
        if(n%3==0) n-=n/3;
        else n-=n/3+1;
    }
    cout << sum << " " << day;
    return 0;
}

谢谢观看！！