CPSJ-1:apple

题目描述

小 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≤109

测试点𝑛≤n特殊性质
1∼210
3∼5103
6∼7106
8∼9106
10109

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

第一种方法:数组遍历,算法复杂度n2,洛谷得分:90分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**************************************************************** 
 * 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分

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**************************************************************** 
 * Description: 2023-CSP-J-simi-1
 * Author: Alex Li
 * Date: 2024-07-01 10:54:08
 * LastEditTime: 2024-07-01 15:46:32
****************************************************************/
#include <iostream>
using namespace std;

int main(){
    int n,sum=0,sum1=0,m;
     cin>>n;
     m=n;
     bool f=true;
    while(f){
      n=n-((n-1)/3+1);
      sum++;
        if(n==3){
            sum+=3;
            break;
        }
        if(n==2){
            sum+=2;
            break;
        }
        if(n==1){
            sum+=1;
            break;
        }
      }
       while((m-1)%3!=0){
          m=m-((m-1)/3+1);
              if(m==3){
              sum1+=3;
              break;
          }
          if(m==2){
              sum1+=2;
              break;
          }
          if(m==1){
              sum1+=1;
              break;
          }
      sum1++;
    }

cout<<sum<<' '<<sum1+1;
}
Scroll to Top