C - Klee in Solitary Confinement--ICPC南京(思维)

81 阅读 0 评论 54 点赞

我是靠谱客的博主认真小天鹅，最近开发中收集的这篇文章主要介绍C - Klee in Solitary Confinement--ICPC南京(思维)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接:

Klee in Solitary Confinement - Gym 103470C - Virtual Judge

题意:

给定n和k，有一个长度为n的序列，可对序列中任意一段连续区间加k，也可以选择不加，使序列众数的个数最大。

思路:

一开始想的是找连续的x个相等的数y，然后答案就是max(nums[y+k]+x)，但后来发现了反例，比如k=1,4 0 -1 3 3 2 2 3 -1 2 2 3 3，这个时候l，r分别是取第一个2和最后一个2的时候是最优的。

首先遍历一遍序列，求出每个数对应的个数，保存在数组nums中，如果k==0，那我们直接输出数量最大值就可以了，否则的话，再从头开始遍历序列，用add数组记录当前的值有多少个是通过加k得到的，然后假设当前遍历到的数为x，然后选择对这个数进行加k，那么add[x]就减1，add[x+k]加1，但如果add[x]减完1小于0了，就要把add[x]重新置零，因为它都为负数了我从下一个端点作为+k得到x的开始比算上之前的要优，比如以k=1，2 3 3 0 2 2 2 1为例。

i=1，add[2]-- => add[2]=-1 => add[2]=0，add[3]++ => add[3]=1

i=2，add[3]--=>add[3]=0，add[4]++ => add[4]=1

i=3，add[3]--=>add[3]=-1 这个时候后面再有加k得到3最优区间就不如从后面为起始好了，以后面为起始开始值为0比当前位置接着算少一个减1。

这里在用存储的时候要加一个偏置bias。

代码:

#include <bits/stdc++.h>

using namespace std;

const int N=4e6+10;
const int bias=2e6;
int n,k;
int nums[N],add[N],a[N];
int main(){
	scanf("%d%d",&n,&k);
	int tt,ma=0;
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		nums[a[i]+bias]++;
		if(nums[a[i]+bias]>ma)
			ma=nums[a[i]+bias];
	}
	if(k==0){
		printf("%d",ma);
		return 0;
	}
	for(int i=1;i<=n;i++){
		add[a[i]+bias]--;
		if(add[a[i]+bias]<0)
			add[a[i]+bias]=0;
		add[a[i]+k+bias]++;
		ma=max(ma,nums[a[i]+bias+k]+add[a[i]+k+bias]);
	}
	printf("%d",ma);
}