Codeforces Round #579 (Div. 3) E. Boxers (贪心)

题意:给你一组数,每个数都可以进行一次加一减一,问最后最多能有多少不同的数.
题解:我们可以用桶存每个数的次数,然后枚举\([1,150001]\)来求对答案的贡献,然后贪心,这里我们不用担心其他乱七八糟的东西,直接根据桶中的个数来求贡献即可,但是要先选\(i-1\)的情况,因为后面的数取不到\(i-1\),假如我们不选\(i-1\),而是选了\(i\)和\(i+1\),后面的数可能会冲突不能选,而\(i\)和\(i+1\)就没必要考虑选择顺序了,因为无论他们和后面的数冲不冲突,对答案的贡献都是一样的.

代码:

int n;

int tot[N];

bool st[N];

int main() {

    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

	cin>>n;

	rep(i,1,n){

		int x;

		cin>>x;

		tot[x]++;

	}

	int res=0;

	rep(i,1,150010){

		if(tot[i]==0) continue;

		if(i==1){

			if(tot[1]>=2){

				st[1]=true;

				st[2]=true;

				res+=2;

			}

			else if(tot[1]==1){

				st[1]=true;

				res++;

			}

		}

		else{

			if(tot[i]==1){

				if(!st[i-1]) {res++;st[i-1]=true;}

				else if(!st[i]) {res++;st[i]=true;}

				else if(!st[i+1]) {res++;st[i+1]=true;}

			}

			else if(tot[i]==2){

				int cnt=0;

				if(!st[i]) {res++;st[i]=true;cnt++;}

				if(!st[i-1]) {res++;st[i-1]=true;cnt++;}

				if(cnt==2) continue;

				if(!st[i+1]) {res++;st[i+1]=true;}

			}

			else{

				if(!st[i]) {res++;st[i]=true;}

				if(!st[i-1]) {res++;st[i-1]=true;}

				if(!st[i+1]) {res++;st[i+1]=true;}

			}

		}

	}

	cout<<res<<'\n';

    return 0;

}

巴特西

Codeforces Round #579 (Div. 3) E. Boxers (贪心)

最新文章

热门文章