题目描述
小Y的桌子上放着n个苹果从左到右排成一列，编号为从1到n。
小苞是小Y的好朋友，每天她都会从中拿走一些苹果。
每天在拿的时候，小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。
随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道，多少天能拿完所有的苹果，而编号为n的苹果是在第几天被拿走的？
输入格式
从文件apple.in中读入数据。
输入的第一行包含一个正整数，表示苹果的总数。
输出格式
输出到文件apple.out中。
输出一行包含两个正整数，两个整数之间由一个空格隔开，分别表示小苞拿走所有苹果所需的天数以及拿走编号为n的苹果是在第几天。
输入输出样例
输入样例1： 8 输出样例1： 5 5说明
样例1解释：
小苞的桌上一共放了8个苹果。
小苞第一天拿走了编号为1、4、7的苹果。
小苞第二天拿走了编号为2、6的苹果。
小苞第三天拿走了编号为3的苹果。
小苞第四天拿走了编号为5的苹果。
小苞第五天拿走了编号为8的苹果。
数据范围：
对于所有测试数据有：1 ≤ n ≤ 10^9。
特殊性质：小苞第一天就取走编号为n的苹果。
耗时限制1000ms 内存限制512MB
解析考点：数学
90 分解法：
类似约瑟夫问题的模拟去标记处理，对于 90% 的测试数据，n≤10^6，开一个 10^6\数组即可做标记。然后循环处理标记数组，因为每一轮都会去掉 1/3 的苹果。因此最多循环 log3/210^6 次。
思路分析：
找规律的题。题目有两问：
苹果什么时候拿完？编号为 n 的苹果是在第几轮被拿走的？对于第一问，容易发现，按拿走的规则看，每三个苹果就会拿走一个苹果。因此，每一轮拿走的苹果数量是⌈n/3⌉。也就是每次都至少拿走三分之一的苹果。如此，我们可以直接循环修改 n 并计数，就可以在 O(log2/3n) 时间复杂度下求出第一问。
对于第二问，容易发现，编号为 n 的苹果只要在当前一轮中没有被拿走，那么在下一轮中，它仍旧是最后一个苹果。对于 n 号苹果，如果它所在的位置 mod3 为 1，那么就会被拿走。因此，我们在第一问的循环修改中直接判断 n 即可确定 n 号苹果是在第几轮被拿走的。
时间复杂度：O(log2/3n)
参考代码：
#includeusing namespace std;int n, day, ans;int main(){cin >> n;int m = n; // 当前苹果数量while(m) { // n 号苹果在每一轮都是最后一个苹果，也就是第 m 个苹果day++;if(m%3==1 && !ans) ans = day; // n 号个苹果在这一天被拿走m -= (m+3-1)/3; // 向上取整}cout > d;for(int i = 1; i < n; i++) cin >> v[i];for(int i = 1; i < n; i++) {cin >> a[i];mi = min(mi, a[i]);dis += v[i]; // 当前总里程if(dis < sum) continue; // 坑点，可能剩余的油够到下一个站点，不需加油long long oil = (dis-sum+d-1)/d; // 需要再加的油sum += oil * d;// 当前总共加的油能够走的里程数ans += oil * mi; // 总花费}cout M;for(int i = 1; i < 3005; i++) x[i] = i*i;while(T--) {int a, b, c;cin >> a >> b >> c;int d = b*b - 4*a*c; // deltaif(b == 0 && c == 0) {cout k;for(int i = 1, u,v,w; i > u >> v >> w;g[v].push_back({u,w});}int l = 0, r = 2e6, mid, ans = -1;while(l m >> k;for(int i = 1, u,v,w; i > u >> v >> w;g[u].push_back({v,w});}dij(1); // spfa(1);if(dis[n][0] == 0x3f3f3f3f) dis[n][0] = -1;cout