[程式] codeforces 1321C: Remove Adjacent

[題意]

給一個由小寫字母組的字串 s (長度介於 1 ~ 100)，每次你可以從 s 中刪掉一個滿足特定條件的字母，問最多能刪掉幾個?

刪除字母的條件：令 s[idx] 為 s 的第 idx 的字母。若 s[idx - 1] 或 s[idx + 1] 的字母其字母順序 (令字母順序為 a -> b -> c -> ... -> x -> y -> z) 在 s[idx] 的字母順序的前一個，則我們可以刪掉 s[idx]

實際看個例子的話，假設 s = "bbcdaa"，則

1. 第一次我們可以刪掉 d (因為 d 的左邊有 c)，得到新的字串 "bbcaa"
2. 第二次可以刪掉 c (因為 c 的左邊有 b)，得到新的字串 "bbaa"
3. 第三次可以刪掉 b (因為 b 的右邊有 a)，得到新的字串 "baa"
4. 第四次再刪掉一個 b (因為這個 b 右邊變成是 a)，得到新的字串 "aa"

因為沒有字母滿足條件了，所以答案是 4。

這題解法其實也很簡單，刪掉的字母依照字母順序由後往前，也就是說

1. 先看 s 中有沒有字母 z，以及能不能刪
2. 再來看有沒有字母 y 可以刪
3. ... 依此類推

其中的概念在於假設所有可以刪掉的字母 z 都已經刪光了，要開始刪掉字母 y 的時候，這時候可以確定 s 中再也不可能有字母 z 能因為後續從 s 中刪掉某些字母又可以被刪掉，所以只要依照字母順序由後往前走一遍即可。從上面的例子來看就能發現，刪掉字母的順序一定要照著上面列的步驟，不然就會少。但是照著順序的話就絕對不會漏

另一個要注意的點可以參考上面例子刪掉 b 的時候的狀況：刪掉一個字母時可能會有連鎖反應，所以要一直檢查到再也沒有字母可以刪了才能往下去檢查下一個字母順序。


實作結果如下

	/*
	* =====================================================================================
	*
	* Filename: 1321C.cpp
	*
	* Description: codeforces 1321C. Remove Adjacent
	*
	* Version: 1.0
	* Created: 2020年03月12日
	* Revision: none
	* Compiler: gcc
	*
	* Author: lionking
	* Organization: None
	*
	* =====================================================================================
	*/
	#include <stdio.h>
	#define MAX_S 128
	int main()
	{
	int len, idx = 0, result = 0;
	char s[2][MAX_S] = {"", ""};
	scanf("%d\n", &len);
	fgets(s[idx]+1, MAX_S, stdin);
	for (char c = 'z'; c >= 'a'; ) {
	for (int i = 1; i <= len; ++i) {
	if (s[idx][i] != c) { continue; }
	if ((c - s[idx][i-1] == 1) || (c - s[idx][i+1] == 1)) {
	s[idx][i] = 0;
	}
	}
	int new_len = 0;
	for (int i = 1; i <= len; ++i) {
	if (s[idx][i] == 0) { continue; }
	s[idx ^ 1][++new_len] = s[idx][i];
	}
	if (new_len == len) { --c; }
	else { result += len - new_len; }
	len = new_len;
	idx ^= 1;
	}
	printf("%d\n", result);
	return 0;
	}

view raw codeforces-1321C.c hosted with ❤ by GitHub