奇怪的球 时限：1s 空间：256m

Question

奇怪的球 时限：1s 空间：256m
文景收到了N（1≤N≤4×10^5）个奇怪的球，球摆成一列，每个球的表面都写着一个数字，第i个球的表面数字是a[i]（2≤a[i]≤4×10^5）。

文景准备将所有的球从1到N依次放入桶中。桶是圆柱形的，底面是封死的，只能从圆柱形顶端放入。桶比较窄，桶中的球只能全部竖着叠放。

文景在放球的过程中，奇怪的事情发生了，如果桶中有连续x个值为x的球，这些球将会消失。

请你帮助文景计算出，从1到N依次放入每个球后，桶中的球有多少个？

输入格式
第一行一个正整数N；

第二行N个正整数，从1到N依次表示每个球表面的数字。

【时间限制、数据范围及描述】：

时间：1s 空间：256M

对于30%的数据：1≤N≤10^4；2≤a[i]≤100；

对于100%的数据：1≤N≤4×10^5；2≤a[i]≤4×10^5；

输出格式
输出N行，每行一个整数，第i行表示放完第i个球后桶中球的个数。

输入/输出例子1
输入：

5

3 2 3 2 2

输出：

1

2

3

4

3

输入/输出例子2
输入：

10

2 3 2 3 3 3 2 3 3 2

输出：

1

2

3

4

5

3

2

3

1

0

样例解释
考虑样例1：

第1个球放入后，桶中球从下至上依次为：3

第2个球放入后，桶中球从下至上依次为：3 2

第3个球放入后，桶中球从下至上依次为：3 2 3

第4个球放入后，桶中球从下至上依次为：3 2 3 2

第5个球放入后，桶中球从下至上依次为：3 2 3

#include<bits/stdc++.h>
using namespace std;
long long n;
int main(){
    scanf("%lld",&n);
    vector<long long>a(n);
    vector<long>bucket;
    for(long long i=0;i<n;i++){
        scanf("%lld",&a[i]);
    }
    for(long long i=0;i<n;i++){
        bucket.push_back(a[i]); 
        long long count=1;
        for(long long j=bucket.size()-2;j>=0&&bucket[j]==a[i];j--){
            count++;
        }
        if(count==a[i]){
            bucket.erase(bucket.end()-count,bucket.end()); 
        }
        printf("%d\n",bucket.size());
    }
    return 0;
}

天才们，帮我看看哪错了，求帮助┭┮﹏┭┮

Answer 1

🕒下午好，题主！目前：🟢[在线]
📢参考GPT-4o mini 模型、由清水白石008整理提供！
📣今日金句：“成功是由不断追求卓越的精神所驱动的。”** — 史蒂夫·乔布斯

你的代码在处理球的消失逻辑时有一些问题。以下是改进后的代码，确保在每次放入球后正确处理连续相同球的消失逻辑：

改进后的代码

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

int main() {
    long long n;
    scanf("%lld", &n);
    vector<long long> a(n);
    vector<pair<long long, long long>> bucket; // 使用pair来存储球的值和连续个数

    for (long long i = 0; i < n; i++) {
        scanf("%lld", &a[i]);
    }

    for (long long i = 0; i < n; i++) {
        if (!bucket.empty() && bucket.back().first == a[i]) {
            bucket.back().second++; // 增加连续相同球的个数
            if (bucket.back().second == a[i]) {
                bucket.pop_back(); // 如果连续个数等于球的值，则移除这些球
            }
        } else {
            bucket.push_back({a[i], 1}); // 新的球入桶
        }
        printf("%lld\n", bucket.size());
    }

    return 0;
}

解释代码

1. 使用pair存储球的值和连续个数：

   • vector<pair<long long, long long>> bucket 用于存储球的值和连续个数。
   • bucket.back().first 表示球的值，bucket.back().second 表示连续相同球的个数。

2. 处理球的消失逻辑：

   • 如果当前球与桶顶的球相同，则增加连续相同球的个数。
   • 如果连续相同球的个数等于球的值，则移除这些球。
   • 否则，将新的球入桶，并将连续个数初始化为1。

3. 输出桶中球的个数：

   • 每次放入球后，输出桶中球的个数。

示例解释

考虑样例1：

• 第1个球放入后，桶中球从下至上依次为：3
• 第2个球放入后，桶中球从下至上依次为：3 2
• 第3个球放入后，桶中球从下至上依次为：3 2 3
• 第4个球放入后，桶中球从下至上依次为：3 2 3 2
• 第5个球放入后，桶中球从下至上依次为：3 2 3

希望这些改进能帮助你解决问题。如果你有任何疑问或需要进一步的帮助，请随时告诉我！