Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3) C.(思维题-贪心)

本文主要是介绍Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3) C.(思维题-贪心)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目

思路来源

https://blog.csdn.net/hzerotole/article/details/111478668

题解

首先，要证明①倒数第二个一定是减②倒数第一个一定是加

③还要证明前面的符号可以任意选，

感觉思路来源证明的很好，自己在做的时候只是手动找了一下规律，

数学归纳法可以证明①-②，但是自己不会证③

证明完之后，对于要凑的t，贪心即可

代码1

类似钟摆，最终的目的是0，如果为正就减，为负就加，

由于成倍数关系，所以远0的方向仍然需要后续被走回，一定不优

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
ll t,a[N];
char s[N]; 
ll cal(char x){
	return 1<<(x-'a');
}
int main(){
	scanf("%d%lld",&n,&t);
	scanf("%s",s+1);
	t-=cal(s[n]);
	t+=cal(s[n-1]);
	m=n-2;
	for(int i=1;i<=m;++i){
		a[i]=cal(s[i]);
	}
	sort(a+1,a+m+1,greater<ll>());
	for(int i=1;i<=m;++i){
		if(t>=0)t-=a[i];
		else t+=a[i];
	}
	puts(!t?"Yes":"No");
	return 0;
}

代码2

考虑n个数先全减，然后对于那些原本需要加的数，需要加2倍

这样就变成了一个套路问题，剩下需要加的值贪心加即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m;
ll t,a[N];
char s[N]; 
ll cal(char x){
	return 1<<(x-'a');
}
int main(){
	scanf("%d%lld",&n,&t);
	scanf("%s",s+1);
	t-=cal(s[n]);
	t+=cal(s[n-1]);
	m=n-2;
	for(int i=1;i<=m;++i){
		a[i]=cal(s[i]);
		t-=a[i];
		a[i]<<=1;
	}
	sort(a+1,a+m+1,greater<ll>());
	t=-t;
	for(int i=1;i<=m;++i){
		if(t>=a[i]){
			t-=a[i];
		}
	}
	puts(!t?"Yes":"No");
	return 0;
}

这篇关于Codeforces Round #692 (Div. 1, based on Technocup 2021 Elimination Round 3) C.(思维题-贪心)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！