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

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]（或者已经是最后一个数字），则比较sum和a[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不可能出现在输入的数字序列中，所以它提供了一个可靠的终止处理的标记。