信息学奥赛一本通 2098：【23CSPJ普及组】小苹果(apple) | 洛谷 P9748 [CSP-J 2023] 小苹果
【题目链接】
洛谷 P9748 [CSP-J 2023] 小苹果
ybt 2098：【23CSPJ普及组】小苹果(apple)
【题目考点】
1. 数学计算
【解题思路】
每天每隔两个苹果拿一个苹果，设共有n个苹果，那么拿走的苹果为第1, 4, 7, …, 3k+1个苹果。
也可以理解为：将n个苹果分为每3个一组，最后几个苹果不足3个也算一组，拿走每组的第1个苹果，共拿走
⌈
n
3
⌉
\lceil \frac{n}{3} \rceil
⌈3n⌉个苹果。
不断循环，每次循环使n减少
⌈
n
3
⌉
\lceil \frac{n}{3} \rceil
⌈3n⌉，n为0时跳出，使用变量day记录循环的次数，循环的次数就是拿苹果的天数。
设dn表示拿走第n个苹果的天数，初值为0。
- 如果dn为0，且这一天苹果数n满足 n % 3 = = 1 n\%3 == 1 n%3==1，也就是最后一个苹果是某一组的第1个苹果，那么在这一天最后一个苹果就会被取走，变量dn记录最后一个苹果被取走的天数。
- 如果dn不为0，则说明已经记录过了，不再进行记录。
最后输出day和dn。
每次循环n减少大约n/3个数字，时间复杂度为 O ( log n ) O(\log n) O(logn)
【题解代码】
解法1：
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, dn = 0, day = 0;//dn：最后一个苹果被拿走的天数 day：拿苹果的总天数
cin >> n;
while(n > 0)
{
day++;
if(n%3 == 1 && dn == 0)
dn = day;
n -= 1+(n-1)/3;//n减去n/3向上取整
}
cout << day << ' ' << dn;
return 0;
}
原文地址：https://blog.csdn.net/lq1990717/article/details/142703939
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！