[C++知识库]Codeforces Round #787 (Div. 3) E. Replace With the Previous Minimize

E. Replace With the Previous, Minimize

方法很多，这里是并查集的一种写法

要使字典序越小越好，我们肯定是从左往右遍历优先把前面的变成a，假设我们把x(x > a)变成a,那么在[a, x]中的所有字母都可以变成a，我们只需要把这些字母的祖宗结点修改为a即可。当$i>=2$的时候，我们后面的就不需要变成a，只需要变成之前变成a的最大那个字母，所以我们需要一直更新之前变成a的最大字母。

int find(int x){
	if(p[x] != x) p[x] = find(p[x]);
	return p[x];
}
char ans[N];

void solve()
{
	for(int i = 1; i <= 26; i ++ ){
		p[i] = i;
	}	
	scanf("%d %d",&n, &m);
	scanf("%s", str + 1);
	for(int i = 1; i <= n; i ++ ) a[i] = str[i] - 'a' + 1;
	int minn = 1;
	for(int i = 1; i <= n; i ++ ){
		if(a[i] <= minn) continue;
		int cha = a[i] - minn;
		if(m >= cha){
			for(int j = 1; j <= a[i]; j ++ ){
				p[find(j)] = find(1);

			}
			m -= cha;
			minn = a[i];
		}else{
			int ave = a[i] - m;
			for(int j = ave; j <= a[i]; j ++ ){
				p[find(j)] = find(ave);
			}
			break;
		}
	}
	for(int i = 1; i <= n; i ++ ){
		ans[i] = find(a[i]) + 'a' - 1;
		printf("%c", ans[i]);
	}
	puts("");
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖