《小苹果》 题解

· · 题解

明显，这签到题。

思路：

肯定不能直接模拟，复杂度爆炸。

我们来想正解，首先，每天都会拿走 1, 4, 7, \cdots 号苹果（如果存在），所以每天都会减少 \lfloor {(n - 1) \div 3}\rfloor + 1 个苹果。所以统计天数的时候，我们设置终止条件 n = 0，在终止前每天更新 n 与其天数。

再看最后一个什么时候被取走。我们应该想到的是，如果最后一个被拿走，那么 n 应当满足 (n - 1) \bmod 3 = 0。由于我懒得打标记，所以只用每次取 \min 即可（因为在前面的某一天拿走后，一定不会在后面再次被拿走）。

然后这道题目就解决了。

代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, day = 0, pick = 0x3f3f3f3f;
    cin >> n;
    while(n)
    {
        day ++;
        if((n - 1) % 3 == 0) pick = min(pick, day);
        n = n - ((n - 1) / 3 + 1);
    }
    cout << day << " " << pick << endl;
    return 0;
}

友情提示：

刚才在群里看三四个人说代码为什么 Luogu 90 pts，但是交到 CCF 就爆零了。

这个问题是这样的：Luogu 等 OnlineJudge 默认采用动态内存，如果你开了但是你不访问这部分不计入程序占用内存。但是 CCF 评测的时候使用了静态内存，你开多大他就算你多大，所以 1e9 + 10 就很明显 MLE 了。