复赛一：小苹果(apple)

信息学奥赛历年真题 2023年CSP普及组真题复赛一：小苹果(apple)

洛谷：P9748
OJ：P4978

题目描述

小 Y 的桌子上放着n 个苹果从左到右排成一列，编号为从1 到n。
小苞是小 Y 的好朋友，每天她都会从中拿走一些苹果。
每天在拿的时候，小苞都是从左侧第1 个苹果开始、每隔 2 个苹果拿走 1 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道，多少天能拿完所有的苹果，而编号为n 的苹果是在第几天被拿走的？

输入格式

输入的第一行包含一个正整数 n，表示苹果的总数。

输出格式

输出一行包含两个正整数，两个整数之间由一个空格隔开，分别表示小苞拿走所有苹果所需的天数以及拿走编号为 𝑛n 的苹果是在第几天。

输入输出样例

输入 8

输出 5 5

说明/提示

【样例 11 解释】

小苞的桌上一共放了 8 个苹果。
小苞第一天拿走了编号为 1、4、7 的苹果。
小苞第二天拿走了编号为 2、6 的苹果。
小苞第三天拿走了编号为 3 的苹果。
小苞第四天拿走了编号为 5 的苹果。
小苞第五天拿走了编号为 8 的苹果。

【数据范围】

对于所有测试数据有：1≤n≤10⁹。

测试点	𝑛≤n≤	特殊性质
1∼2	10	无
3∼5	10³	无
6∼7	10⁶	有
8∼9	10⁶	无
10	10⁹	无

特殊性质：小苞第一天就取走编号为 n 的苹果。

第一种方法：数组遍历，算法复杂度n²，洛谷得分：90分

/**************************************************************** 
 * Description: 2023  CSP-simi-01
 * Author: Alex Li
 * Date: 2024-07-01 10:54:08
 * LastEditTime: 2024-07-01 15:33:52
****************************************************************/
#include <iostream>
#include <vector>
using namespace std;
vector<int> apple;
int main(){
    int n,sum=0,c;
    int i,j;
     cin>>n;
    vector<int> apple(n,1);
    bool f=true;
   
    while(f){
        sum++;
        f=false;
        i=0;
        while(apple[i]==0)i++;
        j=0;
        while(i<n){
              if(apple[i]!=0){
              if(j%3==0){
                apple[i]=0;
                if(i==n-1)c=sum;
                f=true;
              }
                i++;
                j++;
               }else{
                i++;
               }
            }
        }
    
cout<<sum-1<<' '<<c;
}

第二方法：数论方法，算法复杂度：nlogn，洛谷分数： 100分

下面是对这段代码的分析和注释，解释程序的逻辑和关键部分：

代码分析：

变量定义：
- n：输入的苹果总数。
- sum：计算小苞需要多少天才能拿完所有苹果。
- sum1：用于计算编号为 n 的苹果在第几天被拿走。
- m：保存苹果总数 n 的初始值，用于后续计算。
主循环逻辑：
- 程序通过每隔 2 个苹果拿走 1 个苹果的规则，递减剩余苹果数量 n，并计算所需的天数。
- 当剩余苹果数变为 3、2 或 1 时，程序直接计算剩余天数，并终止循环。
编号为 n 的苹果被拿走的天数：
- 第二个循环模拟编号为 n 的苹果在每天小苞拿苹果时是否被拿走，直到 m 达到 1。
- 程序同样判断 m 剩余的苹果数是否为 3、2、1，分别计算相应的天数。
输出：
- 程序输出两项结果：总共需要的天数和编号为 n 的苹果被拿走的第几天。

代码实现：

#include <iostream>
using namespace std;

int main(){
    // 打开输入文件和输出文件
    freopen("apple.in","r",stdin);   // 从 "apple.in" 文件读取输入
    freopen("apple.out","w",stdout); // 将输出写入 "apple.out" 文件

    int n, sum = 0, sum1 = 0, m;     // 定义变量：n 是苹果的总数，sum 记录天数，sum1 记录编号为 n 的苹果在第几天被拿走，m 用于复制 n
    cin >> n;                        // 读取苹果总数 n
    m = n;                           // 备份 n 的值到 m，用于后面计算编号为 n 的苹果被拿走的天数
    bool f = true;                   // 定义一个标志变量 f，用于控制循环的结束条件

    // 计算拿完所有苹果所需的天数
    while(f){                        
        n = n - ((n - 1) / 3 + 1);   // 每天小苞拿走 (n-1)/3 + 1 个苹果，n 是剩下的苹果数
        sum++;                        // 天数加一
        // 根据剩余苹果的数量，判断何时能拿完所有苹果
        if(n == 3){                   // 如果剩下 3 个苹果，后面还需要 3 天才能全部拿完
            sum += 3;                 // 加上剩下的天数（3天）
            break;                    // 结束循环
        }
        if(n == 2){                   // 如果剩下 2 个苹果，后面还需要 2 天才能全部拿完
            sum += 2;                 // 加上剩下的天数（2天）
            break;                    // 结束循环
        }
        if(n == 1){                   // 如果剩下 1 个苹果，后面还需要 1 天才能全部拿完
            sum += 1;                 // 加上剩下的天数（1天）
            break;                    // 结束循环
        }
    }

    // 计算编号为 n 的苹果在第几天被拿走
    while((m - 1) % 3 != 0){          // 判断编号为 n 的苹果是否在每次被跳过 2 个之后被拿走
        m = m - ((m - 1) / 3 + 1);    // 每隔两个苹果拿走一个，减少剩余的苹果数
        if(m == 3){                   // 如果剩下 3 个苹果，苹果 n 将在第 3 天被拿走
            sum1 += 3;                // 加上 3 天
            break;                    // 结束循环
        }
        if(m == 2){                   // 如果剩下 2 个苹果，苹果 n 将在第 2 天被拿走
            sum1 += 2;                // 加上 2 天
            break;                    // 结束循环
        }
        if(m == 1){                   // 如果剩下 1 个苹果，苹果 n 将在第 1 天被拿走
            sum1 += 1;                // 加上 1 天
            break;                    // 结束循环
        }
        sum1++;                       // 每次循环时天数加一
    }

    // 输出总天数和编号为 n 的苹果被拿走的天数
    cout << sum << ' ' << sum1 + 1;   // 输出总天数 sum 和苹果 n 被拿走的第几天 sum1 + 1
}

Previous Lesson

Back to Lesson

Next Topic