Codeforces Global Round 11 B. Chess Cheater（贪心）

时间：2024-08-10 12:35:32

题目链接：https://codeforces.com/contest/1427/problem/B

题意

给出一个长为 \(n\) 由 W, L 组成的字符串，如果一个 W 左侧为 W，则它提供 2 分，否则为 1 分。最多可以将 \(k\) 个 L 变为 W，问字符串可以得到的最大分值。

题解

本题的关键是字符串中 W 的有无及两两构成的封闭区间长度。

  • 如果全为 L，则字符串的最大分值为 \(max(2k-1,\ 0)\) 。
  • 如果存在 W，则每次操作都会至少增加 2 分，如果操作的为两个 W 区间内的最后一个 L，则会额外再增加 1 分。

    所以计算字符串的初始分值，加上 \(2 \times min(k, cntL)\) 分，然后区间长度排序，每当可以减去一个完整区间长就再加上 1 分。

代码

#include <bits/stdc++.h>

using namespace std;

int main() {

	ios::sync_with_stdio(false);

	cin.tie(nullptr);

	int t;

	cin >> t;

	while (t--) {

		int n, k;

		cin >> n >> k;

		string s;

		cin >> s;

		int cntL = count(s.begin(), s.end(), 'L');

		if (cntL == n) {

			cout << max(2 * k - 1, 0) << "\n";

			continue;

		}

		vector<int> posW;

		for (int i = 0; i < n; i++)

			if (s[i] == 'W') posW.push_back(i);

		vector<int> seg;

		for (int i = 1; i < int(posW.size()); i++)

			if (posW[i] - posW[i - 1] - 1 > 0) seg.push_back(posW[i] - posW[i - 1] - 1);

		int ans = s[0] == 'W';

		for (int i = 1; i < n; i++)

			if (s[i] == 'W') ans += s[i - 1] == 'W' ? 2 : 1;

		ans += 2 * min(k, cntL);

		sort(seg.begin(), seg.end());

		for (auto len : seg) if (k >= len) k -= len, ans += 1;

		cout << ans << "\n";

	}

	return 0;

}