2 条题解

  • 0
    @ 2025-3-10 22:00:59

    问题分析

    本题涉及一个间隔采摘的过程,并要求计算:

    1. 总共需要多少天才能摘完所有果实
    2. 编号 2025030320250303 的果实在第几天被摘走

    核心操作

    • 第一天,dash 采摘编号 11 的果实,并且每间隔 22 个果实就再摘一个,即每 33 个果实取一个。
    • 采摘后,剩余的果实按照原顺序重新排列,进入下一天。
    • 继续按照相同的规则进行采摘,直到所有果实被摘完。

    由于每轮的采摘遵循固定模式,本题的解法涉及模拟 + 数学推导

    算法解析

    这个问题可以归结为一个特殊的消除序列问题,其中每一轮按固定规则减少元素。

    第一步:计算总天数

    假设当前剩余果实数为 mm,每一轮中,dash 会按照33 个取一个的策略采摘果实,实际摘除的果实数为:

    m3\left\lceil \frac{m}{3} \right\rceil

    其中 x\left\lceil x \right\rceil 代表向上取整。每轮摘取后,剩余果实数更新为:

    m=mm3m = m - \left\lceil \frac{m}{3} \right\rceil

    直到 m=0m=0 为止,即所有果实被摘完,这一过程的天数即为最终所需的天数

    第二步:确定编号 2025030320250303 被摘取的天数

    由于编号 nn 的果实在采摘规则下会不断向右侧移动,我们需要确定它在哪一天被采摘。

    在每一天:

    • 果实总数减少 m3\left\lceil \frac{m}{3} \right\rceil
    • 如果编号 nn 是本轮序列中的第 mm 个(即最后一个),则此时被摘取,我们记录下此时的天数。

    利用上述思路,我们可以在模拟过程中,同时计算总天数目标果实的摘取时间

    #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
    上传者