线上OJ:
https://www.jisuanke.com/problem/T3917 (opens in a new tab)
https://www.luogu.com.cn/problem/P9748 (opens in a new tab)
题目分析:
- 第一问:几天拿完 直接计算每一天拿去后的苹果个数,设拿之前有 n 个苹果,拿完后剩 n − ⌈3/n⌉(向上取整) 个苹果。
- 第二问:编号为n的苹果(即:最后一个苹果)在第几天被拿走 设每一天有 n 个苹果,当 n mod 3 == 1 时即可,且第一次出现。
💡
向上取整 的代码 ,所以每天最少拿走多少个为
核心思想:
由于从编号 1开始,每隔 2个取走1个,所以实际是每3个取走1个...
假设每一轮开始前的总数为 m,由数学归纳法得这一轮要取走的数量是 (m+2)/3 。(因为每一组取走的都是第1个),所以每一轮取走的总数量是 (m+2)/3
比如:当前 m=8, 则
第一轮取走 10/3=3个,剩余5个;
第二轮取走 (5+2)/3=2个,剩余3个,
第三轮取走 (3+2)/3=1个,剩余2个,
第四轮取走(2+2)/3=1个,剩余1个;
第五轮取完
所以第一个问题:几天取完可以根据每天剩余 m-(m+2)/3,while循环直至m变为0
第二个问题问的是 编号为 n 的第几天被取走,由于编号为n的永远是在最后一个,所以当第一次剩余数量 m为3倍余1时,最后一个会被取走,记录此时的天数即可
题解代码:
#include <bits/stdc++.h>
using namespace std;
int n, m;
int cnt = 0; // 第 cnt 天
int day = 0; // 记录编号为n被取走的那天
int main()
{
cin >> n;
m = n;
while(m)
{
cnt++; // 第 cnt 天
if((!day) && (m%3 == 1)) // 如果day还没被更新,且当前总数 m为3的倍数+1,说明本轮的最后一个数会被取走,也就是编号n会被取走
day = cnt;
m -= (m+2) / 3; // 取走 (m+2)/3,剩余 m - (m+2)/3
}
cout << cnt << " " << day;
return 0;
}