PDF文档公众号回复关键字:20241021
1 P9748 [CSP-J 2023] 小苹果
[题目描述]
小 Y 的桌子上放着 n 个苹果从左到右排成一列，编号为从 1 到 n。
小苞是小 Y 的好朋友，每天她都会从中拿走一些苹果。
每天在拿的时候，小苞都是从左侧第 1 个苹果开始、每隔 2 个苹果拿走 1 个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列。
小苞想知道，多少天能拿完所有的苹果，而编号为 n 的苹果是在第几天被拿走的？
[输入格式]
输入的第一行包含一个正整数 n，表示苹果的总数
[输出格式]
输出一行包含两个正整数，两个整数之间由一个空格隔开，分别表示小苞拿走所有苹果所需的天数以及拿走编号为 n 的苹果是在第几天
[输入输出样例]
输入 #1
8
输出 #1
5 5
说明/提示
小苞的桌上一共放了 8 个苹果。
小苞第一天拿走了编号为 1、4、7 的苹果。
小苞第二天拿走了编号为 2、6 的苹果。
小苞第三天拿走了编号为 3 的苹果。
小苞第四天拿走了编号为 5 的苹果。
小苞第五天拿走了编号为 8 的苹果。
数据规模
对于所有测试数据有：1≤n≤10^9
| 测试点 | n≤n≤ | 特殊性质 |
|---|---|---|
| 1∼2 | 10 | 无 |
| 3∼5 | 10^3 | 无 |
| 6∼7 | 10^6 | 有 |
| 8∼9 | 10^6 | 无 |
| 10 | 10^9 | 无 |
2 相关知识点
1) 向上取整
数学符号
⌈ ⌉
⌈x⌉ 向上取整符号 表示大于等于 x 的最小的整数
例如
⌈13/3⌉=5
2) 向下取整
数学符号
⌊ ⌋
⌊x⌋ 向下取整符号 表示小于等于 x 的最大的整数
例如
⌊13/3⌋=4
3 思路分析
思路1-数组模拟
模拟拿苹果的过程
1 按3个一组把苹果分成若干组，每次取每组的第1个苹果，取完苹果打标识，标识此苹果已经被拿
2 从新把剩余苹果分组，按1重新拿，指导拿完
以8个苹果为例子，具体拿的过程如下
1 拿每组(3个)的第1个，拿走1，4，7位置的苹果
2 继续拿每组(3个)的第1个，拿走2，6位置的苹果
3 继续拿每组(3个)的第1个，拿走3位置的苹果
4 继续拿每组(3个)的第1个，拿走5位置的苹果
5 继续拿每组(3个)的第1个，拿走8位置的苹果，第8个苹果，是第5天拿走的
示例程序
#include<bits/stdc++.h>
using namespace std;
const int N=1e6;//90%测试用例满足
/*
a[N]模拟数组，每个苹果放入数组的1个位置，开始为0，如果拿走设置为1
n个苹果
cnt 每一天遍历时 剩余苹果对应的位置
temp 还剩余的苹果数
days 第几天拿苹果
ndays 第n个苹果是第几天拿
*/
int a[N],n,cnt,temp,days,ndays;
int main(){
cin>>n;//输入苹果数n
temp=n;//暂存一份n，拿去后直接从temp上面减去，n保持不变
while(temp){//如果剩余还有苹果 需要继续取苹果
days++;//新的一天拿苹果
cnt=0;//还剩余苹果遍历时从1开始的位置
for(int i=1;i<=n;i++){//重新遍历一遍
if(a[i]==1) continue;//如果此位置苹果已经被拿走，继续拿下一个
cnt++;//拿当前苹果
if(cnt%3==1){//每3个苹果拿第1个
a[i]=1;//标识此苹果已经被拿走
temp--;//剩余苹果少1个
if(i==n){//如果本次拿的是第n个苹果，记录是第几天
ndays=days;//记录第n个苹果是days天拿走的
}
}
}
}
cout<<days<<" "<<ndays;//输出总共拿了几天苹果和第n个苹果是第几天拿走的
return 0;
}
思路2
1 计算每天拿走的苹果数，3个1组，计算方法当前剩余苹果数和3取余向上取整
例如
剩余1个苹果可以拿走1个：⌈1/3⌉=1
剩余2个苹果可以拿走1个：⌈2/3⌉=1
剩余3个苹果可以拿走1个：⌈3/3⌉=1
剩余4个苹果可以拿走2个：⌈4/3⌉=2
2 直到拿完为止
单独计算第几天拿走第n个苹果
1 由于3个1组，每次拿走第1个，所以当剩余苹果中，n为每3个1组中的第1个时，第n个苹果为拿走
2 拿走第n个苹果结束，输出对应第几天
示例程序
#include<bits/stdc++.h>
using namespace std;
/*
n输入n个苹果
x临时变量 每1天拿完苹果后还剩余苹果的数量
days1 第1次模拟第几天拿苹果
days2 第2次模拟第几天拿苹果
*/
int n,x,days1,days2;
int main(){
cin>>n;//输入苹果数n
x=n;//x初始为n
//计算几天拿完苹果
while(x){//还剩余苹果 进入循环拿苹果
days1++;//天数加1
x=x-(x+2)/3;//本次拿苹果数位剩余苹果数/3向上取整
}
cout<<days1<<" ";//几天拿完苹果
//计算第几天拿第n个苹果
while(true){//一直循环 等待break退出
days2++;//记录是第几天拿苹果
if(n%3==1) break;//如果第days天，n可以被拿走 则退出
n=n-(n+2)/3;//不能被拿走，总数去除第days2天拿走的苹果，继续对剩余的苹果继续拿
}
cout<<days2;//输出第n个苹果第days2天拿走
return 0;
}