CF 1082E Increasing Frequency(贪心)

解题思路

　　贪心。对于一段区间中，可以将这段区间中相同的元素同时变成\(c\)，但要付出的代价是区间中等于\(c\)的数的个数，设\(sum[i]\)表示等于\(c\)数字的前缀和，Max[i]表示数字\(i\)的最大个数。那么只要\(O(n)\)的扫一遍，维护一下每个数字的\(max\)，具体做法是看一下\(Max[a[i]]\)大还是\(sum[i]\)大，如果\(sum\)大的话，说明前面都不变，直接把\(Max\)赋值成\(sum[i]+1\)，否则直接让\(Max[i]++\)，然后每次跟后面的\(sum\)并到一起更新一次答案。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<vector>

using namespace std;

const int MAXN = 500005;

inline int rd(){

	int x=0,f=1;char ch=getchar();

	while(!isdigit(ch)) f=ch=='-'?0:1,ch=getchar();

	while(isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();

	return f?x:-x;

}

int n,c,a[MAXN],sum[MAXN],Max[MAXN],ans,pre[MAXN];

inline int max(int x,int y){

	return x>y?x:y;

}

int main(){

	n=rd(),c=rd();int now;

	for(int i=1;i<=n;i++) {

		sum[i]=sum[i-1];a[i]=rd();

		if(a[i]==c) sum[i]++;

	}

	for(int i=1;i<=n;i++){

		if(a[i]==c) continue;

		now=sum[i];

		if(now>=Max[a[i]]) Max[a[i]]=now+1;

		else Max[a[i]]++;

		ans=max(ans,Max[a[i]]+sum[n]-sum[i]);pre[a[i]]=i;

	}

	printf("%d\n",max(ans,sum[n]));

	return 0;

}

巴特西

CF 1082E Increasing Frequency(贪心)

解题思路

代码

最新文章

热门文章