蓝桥杯省赛无忧 编程3 小明和完美序列

发布时间:2024年01月15日

在这里插入图片描述

https://www.lanqiao.cn/problems/3199/learning/?isWithAnswer=true&page=1&first_category_id=1&name=%E5%B0%8F%E6%98%8E%E5%92%8C%E5%AE%8C%E7%BE%8E%E5%BA%8F%E5%88%97

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int a[N];
int main()
{
    int n,i,sum=1,ans=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    a[n+1]=-1;//多加一个使原来最后一个能算进去
    for(i=1;i<=n;i++)
    {
        if(a[i]==a[i+1])
        {
            sum++;
        }
        else
        {
            if(sum>a[i])
                ans+=sum-a[i];
            if(sum<a[i])
                ans+=sum;
            sum=1;
        }
    }
    cout<<ans;
    return 0;
}

这个代码的思路是统计数组中相同数字出现的次数,并且确保这个次数与数字的值相匹配,这样才能形成"完美序列"。若次数与数字的值不匹配,则计算出需要删除的元素数量,以使剩余的序列变为完美序列。下面是这个过程的详细步骤:

  1. 读取数字个数n并从标准输入读取n个整数到数组a中。
  2. 对数组a进行排序,这样相同的数字会排列到一起,方便统计。
  3. a[n+1]设置为-1,这是一种技巧,用来标记数组的末尾,以便最后一个数字能够被正确处理。
  4. 初始化sum为1,sum用来统计当前数字连续出现的次数。
  5. 通过一个循环遍历数组a,在每个步骤中:
    • 如果当前数字a[i]等于下一个数字a[i+1],则sum加1。
    • 如果当前数字a[i]不等于下一个数字a[i+1](或者已经是最后一个数字),则比较suma[i]
      • 如果sum大于a[i],表示有多余的数字,需要删除sum - a[i]个数字。
      • 如果sum小于a[i],表示数字不够,需要删除所有这些数字。
  6. 每次处理完一个数字(或一组相同的数字)后,将sum重置为1,以便统计下一个数字。
  7. 最终,变量ans累加了所有需要删除的元素数量。
  8. 输出ans,即为最少需要删除的数字个数,以形成完美序列。

整个代码的关键在于对数组排序后方便统计每个数字出现的次数,并通过比较每个数字的值和其出现次数来确定删除元素的数量。

在实际使用中,这个代码是有效的,只要保证输入的数字个数n加上1不超过数组a定义的大小N(这里是100005)。这个假设是安全的,因为a[n+1]是代码中人为设置的一个哨兵值,用于处理最后一个数字。由于-1不可能出现在输入的数字序列中,所以它提供了一个可靠的终止处理的标记。

文章来源:https://blog.csdn.net/weixin_74774974/article/details/135609500
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。