2 条题解
-
0
问题分析
本题涉及一个间隔采摘的过程,并要求计算:
- 总共需要多少天才能摘完所有果实
- 编号 的果实在第几天被摘走
核心操作:
- 第一天,dash 采摘编号 的果实,并且每间隔 个果实就再摘一个,即每 个果实取一个。
- 采摘后,剩余的果实按照原顺序重新排列,进入下一天。
- 继续按照相同的规则进行采摘,直到所有果实被摘完。
由于每轮的采摘遵循固定模式,本题的解法涉及模拟 + 数学推导。
算法解析
这个问题可以归结为一个特殊的消除序列问题,其中每一轮按固定规则减少元素。
第一步:计算总天数
假设当前剩余果实数为 ,每一轮中,dash 会按照每 个取一个的策略采摘果实,实际摘除的果实数为:
其中 代表向上取整。每轮摘取后,剩余果实数更新为:
直到 为止,即所有果实被摘完,这一过程的天数即为最终所需的天数。
第二步:确定编号 被摘取的天数
由于编号 的果实在采摘规则下会不断向右侧移动,我们需要确定它在哪一天被采摘。
在每一天:
- 果实总数减少 。
- 如果编号 是本轮序列中的第 个(即最后一个),则此时被摘取,我们记录下此时的天数。
利用上述思路,我们可以在模拟过程中,同时计算总天数和目标果实的摘取时间。
#include<bits/stdc++.h> using namespace std; int n, day, ans; int main() { cin >> n; int m = n; // 当前果实数量 while(m) { // 只要果实还没摘完,就继续循环 day++; // 记录第几天 if(m % 3 == 1 && !ans) ans = day; // 20250303号果实被摘取时记录天数 m -= (m + 3 - 1) / 3; // 计算本轮采摘后剩余的果实数(向上取整) } cout << day << ' ' << ans; return 0; }
import java.util.Scanner; public class FruitPicking { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 读取输入果实总数 scanner.close(); int day = 0; int ans = 0; int m = n; // 剩余果实数量 while (m > 0) { day++; // 记录天数 if (m % 3 == 1 && ans == 0) { ans = day; // 记录20250303号果实被采摘的天数 } m -= (m + 3 - 1) / 3; // 计算采摘后的剩余果实数(向上取整) } System.out.println(day + " " + ans); } }
def fruit_picking(n): day = 0 ans = 0 m = n # 当前果实数量 while m > 0: day += 1 # 记录天数 if m % 3 == 1 and ans == 0: ans = day # 记录20250303号果实被采摘的天数 m -= (m + 3 - 1) // 3 # 计算采摘后的剩余果实数(向上取整) print(day, ans) # 运行函数 n = int(input()) fruit_picking(n)
信息
- ID
- 293
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- 递交数
- 109
- 已通过
- 33
- 上传者