[Educational Codeforces Round 6][Codeforces 620E]New Year Tree
[Testing Round #13][Codeforces 753C] Interactive Bulls and Cows (Hard)

[Educational Codeforces Round 6][Codeforces 620C]Pearls in a Row

Zarxdy34 posted @ 2017年11月22日 16:13 in Codeforces with tags 贪心 , 93 阅读

    题意:给出一个数列,将数列尽可能多地分成若干段,每段至少包含一对相同的数,问最多分成多少段。

    题解:显然的贪心,如果当前数能和前面的尚未被分段的数相等,就以该点为一段的结尾,以保证能分成尽量多的段。(实在看不出来写个DP方程也就很显然了)最后那些没被分段的数放到它们的前一段里去就好了。

 

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;

map <int,int> M;
int a[maxn];
int e[maxn],en;
int n;

int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	for (int i=1;i<=n;i++)
	{
		if (M[a[i]]>e[en]) e[++en]=i;
		M[a[i]]=i;
	}
	if (en==0)
	{
		printf("-1\n");
		return 0;
	}
	e[en]=n;
	printf("%d\n",en);
	for (int i=1;i<=en;i++)
		printf("%d %d\n",e[i-1]+1,e[i]);
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Back to Top