---
tags: 進階班
---

# Greedy 貪心演算法

## 前言

本次的內容非常特別，它不是一個特定的資料結構，也不是一種特定的解法 (例：二分搜、sort 等)

它是一種想法，

由於過於抽象，帶題目來講解會比較好理解

## 概念

對於一個題目，有些可以使用暴力搜尋來解題，

就是窮舉的概念，

但是，**複雜度會卡**，因此除非是只能用暴搜解的題，否則通常都不會過。

那麼，可以透過一些方法剪枝，過濾一些不用想就絕對會錯的組合，藉此降低複雜度來 `AC` 嗎？

**YES**，而 `Greedy` 就有點類似這個方法

它是一種在每步選擇中都採取在當前狀態下最佳的選擇，

從而希望結果是最佳的演算法。

## 帶題目

[a074. 校長室之謎](http://203.64.191.163/ShowProblem?problemid=a074)

以這題範例測資，可以設一個 `sum = 0`

然後開始「吞」數列，首先吞 `3`，`sum = 3`

接下來吞 `6`，`sum = 9`

然後吞 `1`，`sum = 10, ans++`

再吞 `7`，`sum = 17`，超過需要的 `k = 10`，要開始「吐」前面的數字出來了

先吐 `3`，`sum = 14`，不夠多 -> 吐 `6`，`sum = 8`，可以繼續吃了

吃 `2`，`sum = 10, ans++`，陣列結束。

這樣就不會偵測像是 `3 6 1 7 2` 這種 `sum = 19` 一定不會是答案的陣列。

時間複雜度從 $O(N^2) \Rightarrow O(N)$

---

[a094: 發大財！](http://203.64.191.163/ShowProblem?problemid=a094)

這題相對簡單一些，但也是 `greedy` 演算法

基本上就是對第一個字串的每個字元逐一檢測是否在第二個字串裡即可。

(注意指向第二個字串的指針不可「倒轉」，符合 `greedy` 的精神)

:::spoiler `code`

#include<bits/stdc++.h>
#define LL long long
#define f first
#define s second
using namespace std;
int main() {
	cin.tie(nullptr), ios_base::sync_with_stdio(false);
	int T;
	cin >> T; cin.get();
	string str, str2;
	while (T--) {
		size_t tmp = 0;
		cin >> str >> str2;
		bool f = false;
		for (size_t x = 0; x < str2.length(); x++) {
			if (str[tmp] == str2[x]) tmp++;
			if (tmp == str.length()) {f = true; break;}
		}
		cout << ((f) ? "Yes\n" : "No\n");
	}
	return 0;
}

:::