【题解】统计差异

题意

给你一个长度为的数组，中有种不同的数，若则记录加一，现在可以删除一种数使得最终的记录尽量小，问最小的记录是多少。

题意

一个开始总的记录值记为，我们要计算的就是考虑去掉某一种数字所能减少的记录值最大，连续一样的数字都可以合并成一个，例如，就可以转化为。接下来我们考虑的都是处理过的数字，例如对于，这种组合，我们若去掉，答案只会减少，当遇到的是这种情况时，去掉时，答案会减少。遍历一遍处理过的数组，然后记录若去掉该数的贡献是多少。最后遍历找一遍贡献最大的数即可。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N],p[N];
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);
        if(a[i]==a[i-1])
            i--,n--;
    }
    int ans=1;
    for(int i=1; i<=n; i++)
    {
        if(a[i-1]==a[i+1])
            p[a[i]]+=2;
        else
            p[a[i]]++;
    }
    for(int i=1; i<=k; i++)
    {
        if(p[i]>p[ans])
            ans=i;
    }
    printf("%d\n",ans);
    return 0;
}