反转数列

NC223141. 反转数列

描述

给出一个长度为 $N$ 的数列，你每次可以选择一段连续的区间，然后将其反转，求出在最多执行 $K$ 次反转的的前提下，能够得到相邻且不同的数对数的最大值。

例如一个长度为 $5$ 的数列为 $(1,1,1,2,2)$ ，你可以反转区间 $[2,4]$ 得到 $(1,2,1,1,2)$ ，然后再反转区间 $[4,5]$ 得到 $(1,2,1,2,1)$ ，得到了 $4$ 对相邻且不同的数对，而且这也是经过 $2$ 次操作最多可以得到的数对数。

输入描述

第一行给出两个正整数 $N,K$ ，含义如题

第二行给出 $N$ 个正整数 $a_i$ ，表示数列中的 $N$ 个元素

$1 \le N \le 5 \times 10^5$

$0 \le K \le N$

$1 \le a_i \le N$

输出描述

在一行中输出在经过最多  次反转的前提下最多可以得到的相邻且不同的数对数

示例1

输入:

5 2
1 1 1 2 2

输出:

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 64ms, 内存消耗: 3516K, 提交时间: 2021-07-09 22:20:06

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

int a[500005],num[500005]={0},cnt[500005]={0};
int main()
{
	int i,n,m,t=0,s=0,mx=0,ans=0;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		num[a[i]]++,mx=max(mx,num[a[i]]);
	}
	if(2*mx>n+1)mx=2*(n-mx);
	else mx=n-1;
	for(i=1;i<n;i++)
	{
		if(a[i]!=a[i+1])ans++;
		else
		{
			cnt[a[i]]++,s++;
			t=max(t,cnt[a[i]]);
		}
	}
	if(2*t>s)i=s-t;
	else i=s/2;
	while(m--)
	{
		if(i>0)i--,ans+=2;
		else ans++;
	}
	printf("%d\n",min(ans,mx));
	return 0;
}