2023 小苹果 · 方案一照规则真模拟

CSP-J 标程 · 复赛真题 · 代码 · cpp · 难度 1/5 · 共 1016 字

用数组存剩下的苹果，每天挑走一批

2023
模拟

正文

// CSP-J 2023 复赛 T1 · 小苹果
// 原题：https://oj.yecheng.tv/p/CSPJ2023A
// 题意：n 个苹果排成一排。每天从左边第 1 个开始、每隔 2 个拿走 1 个
// （也就是拿走第 1、4、7、... 个），剩下的重新排好，第二天继续。
// 问多少天拿完，以及编号为 n 的那个苹果是第几天被拿走的。
//
// 方案一 · 照着规则真模拟（最直观，n 大时会超时）
// 用一个数组存现在还剩下的苹果编号，每天把下标是 0、3、6、... 的挑走，
// 顺手看看里面有没有编号 n；剩下的原地压缩成一个新数组，进入下一天。
// 每天都要扫一遍数组、还要搬一次数据，总复杂度 O(n^2)，n = 1e9 时既存不下也跑不完。

#include <bits/stdc++.h>
using namespace std;

int main() {
    freopen("apple.in", "r", stdin);
    freopen("apple.out", "w", stdout);

    int n;
    cin >> n;

    vector<int> cur;
    for (int i = 1; i <= n; i++) cur.push_back(i);

    int day = 0;
    int when = 0;
    while (!cur.empty()) {
        day++;
        vector<int> left;
        for (size_t i = 0; i < cur.size(); i++) {
            if (i % 3 == 0) {                 // 第 1、4、7、... 个，今天被拿走
                if (cur[i] == n) when = day;
            } else {
                left.push_back(cur[i]);
            }
        }
        cur = left;
    }
    cout << day << " " << when << "\n";
    return 0;
}

2023 小苹果 · 方案一 照规则真模拟

正文

CSP-J 标程 · 复赛真题的其它内容

2023 小苹果 · 方案一照规则真模拟