CSP-J-2023 T1-小苹果题解

此题为CSP-J 2023 第一题小苹果。题目传送门

做法一

首先阅读题目，发现可以用一个大小为 的数组进行暴力模拟操作，可以先进行数量的枚举，然后在嵌套一层循环进行每天拿苹果的操作。但容易发现数据范围很大，数组开到1e9会 MLE 而也容易 TLE 拿不到满分。

做法二（正解）

首先我们发现，每次拿一个苹果后都需要隔两个苹果在拿下一个苹果。所以数据可以分为 和 两部分

第一部分

第一部分也就是 的情况。我们列几个数字进行分析，如果 为 的情况下可以在第一天就取到编号为 的苹果，易得当 的情况下便可在第一题的得到编号为n的苹果，所以可以在循环内进行判断，如果符合上述条件，那么就标记天数为当前天数。接着我们观察拿苹果后数量的编号，如果 为 那么第一天取完后便剩余 个苹果，如果 为 那么第一天去完后也剩余 个。所以易得取完一天后的苹果数量为 ，通过循环依次向后推即可。

最终时间复杂度为

代码

#include<bits/stdc++.h>
using namespace std;
int n, aday, nday;
int main() {
	cin >> n;
	while (n > 3) {
		aday++;
		if (n % 3 == 1 && !nday) nday = aday;
		if (n % 3 == 0)	n -= n / 3;
		else	n -= n / 3 + 1;
	}
	aday += n;
	if (!nday) nday = aday;
	cout << aday << ' ' << nday << endl;
	return 0;
}