目錄

1.貪心算法的思想

2.區間貪心算法常用的一些題目類型

1.選擇最多不相交區間問題

P2970 [USACO09DEC] Selfish Grazing S

?1.思路分析

2.上代碼

2.區間選點問題

P1250 種樹

1.題目

2.方法一

1.代碼解釋

?3.方法二

3.區間合并問題

P2434 [SDOI2005] 區間

1. 思路分析

2.上代碼

4.區間覆蓋問題

?P1668 [USACO04DEC] Cleaning Shifts S

1.思路分析

?2.代碼解釋

5.區間分組

T471772 cici排課

?編輯?1.一點點思路

2.代碼實現與算法思路

3.舉一反三

3.遇到了(區間)貪心的題我們應該怎么做

end👍🏻?ok?

---

1.貪心算法的思想

貪心算法是從問題的初始狀態出發，通過若干次的貪心選擇而得到的最優值(或較優值)的1種求解問題策略，即貪心策略。

2.區間貪心算法常用的一些題目類型

1.選擇最多不相交區間問題

P2970 [USACO09DEC] Selfish Grazing S

洛谷：P2970 [USACO09DEC] Selfish Grazing S - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)https://www.luogu.com.cn/problem/P2970

?1.思路分析

題題目的大概意思就是給定我們N個區間，求最多不相交區間有多少個。

我們可以按照區間的右端點從小到大排序

?然后我們創建一個變量命名為j和一個變量cnt(計數),再次循環整個結構體(輸入的那些區間,已經排序完), 如果循環到的這個區間的左端點在標簽變量j的右邊,把j更新為這個區間的左端點,cnt++

2.上代碼

#include <bits/stdc++.h>
using namespace std;
struct M{int s,e;
}a[500005];
bool cmp(M x,M y){return x.e <y.e;
}
int main(){int n;cin >> n;for(int i =0; i < n; i++){cin >> a[i].s >> a[i].e;}sort(a,a+n,cmp);int j = -1,cnt = 0;for (int i =0; i < n; i++){if (a[i].s >= j){j = a[i].e;cnt ++;}}cout << cnt;return 0;
}

2.區間選點問題

P1250 種樹

洛谷：

P1250 種樹 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)https://www.luogu.com.cn/problem/P1250

1.題目

?

2.方法一

?把所有樹都往右邊種，為了讓他們重疊區間的更多，而且重疊的部分大部分都在右側，我們就要讓這些區間按右端點，從小到大排序，下圖是我列舉的樣例。

首先先把樣例歸一整一下（排序）

1	2	3	4	5	6	7	8	9
【	|	|	】
		【	|	】
			【	|	】
							【	】

從第一個開始在尾巴上種樹，如果這個區間內已經種到了t[i]棵的話就不種了 , 如果沒有種到這么多棵樹那就得從后往前,循環種樹只要種到為止.(括號代表已經種上樹了，+1代表多種一棵樹)

1	2	3	4	5	6	7	8	9
【	|	(|)+1	（】)+1
		(【)	(|)	(】)被底下的人種上了
			(【)	(|)+1	】
							(【)+1	（】)+1

其實這樣的話更形象,就是有點亂:

1	2	3	4	5	6	7	8	9
([)	|	(|[)	(]|[)	(]|)	]		([)	(])

?同樣顏色是一個區間

貪心加模擬的思想

1.代碼解釋

#include <bits/stdc++.h>
using namespace std;
bool v[100005];
struct Sa{int a,b,c;
}s[100005];
bool cmp(Sa x,Sa y){return x.b < y.b;
}

我定義了一個叫做s的 結構體,s[i].a = b,s[i].b = e,s[i].c = t(這些值和題目中的數);

這一段代碼靠下的cmp是排序函數

v數組就是大街,就是那個有點亂的圖

___________________________優雅的分界線_______________________

輸入+排序?

int main(){int q;int n;cin >> q>> n;for (int i =1; i <= n; i++){cin >> s[i].a >> s[i].b >> s[i].c;}sort(s+1,s+n+1,cmp);

___________________________優雅的分界線_______________________

    int cnt = 0;for (int i = 1; i <= n; i++){int sum = 0;for (int j = s[i].a; j <= s[i].b; j++){if (v[j]) sum ++;}if (sum >= s[i].c){continue;}

?循環的第一部分, sum的值是在這個區間內種了多少棵樹,如果已經種夠了那就不用循環這一次看下一次區間.

___________________________優雅的分界線_______________________

		sum = s[i].c - sum;cnt += sum;for (int j = s[i].b; j >= s[i].a; j--){if (v[j] == 0){sum --;v[j] = 1;}if (sum == 0){break;}}

?循環的第二部分,sum值變成還差多少棵樹,總共棵數增加sum,循環種樹(倒過來循環);

___________________________優雅的分界線_______________________

最后輸出cnt;

___________________________優雅的分界線_______________________

總體代碼

#include <bits/stdc++.h>
using namespace std;
bool v[100005];
struct Sa{int a,b,c;
}s[100005];
bool cmp(Sa x,Sa y){return x.b < y.b;
}
int main(){int q;int n;cin >> q>> n;for (int i =1; i <= n; i++){cin >> s[i].a >> s[i].b >> s[i].c;}sort(s+1,s+n+1,cmp);int cnt = 0;for (int i = 1; i <= n; i++){int sum = 0;for (int j = s[i].a; j <= s[i].b; j++){if (v[j]) sum ++;}if (sum >= s[i].c){continue;}sum = s[i].c - sum;cnt += sum;for (int j = s[i].b; j >= s[i].a; j--){if (v[j] == 0){sum --;v[j] = 1;}if (sum == 0){break;}}}cout << cnt;return 0;
}

?3.方法二

換1種方法可以反過來運算,就像加有減，除有乘

也就是從左到右去種樹，排序的時候按照左端點從小到大排序，

直接演示代碼吧！

#include <bits/stdc++.h>
using namespace std;
bool v[100005];
struct Sa{int a,b,c;
}s[100005];
bool cmp(Sa x,Sa y){return x.a > y.a;
}
int main(){int q;int n;cin >> q>> n;for (int i =1; i <= n; i++){cin >> s[i].a >> s[i].b >> s[i].c;}sort(s+1,s+n+1,cmp);int cnt = 0;for (int i = 1; i <= n; i++){int sum = 0;for (int j = s[i].a; j <= s[i].b; j++){if (v[j]) sum ++;}if (sum >= s[i].c){continue;}sum = s[i].c - sum;cnt += sum;for (int j = s[i].a; j <= s[i].b; j++){if (v[j] == 0){sum --;v[j] = 1;}if (sum == 0){break;}}}cout << cnt;return 0;
}

3.區間合并問題

P2434 [SDOI2005] 區間

網址：

P2434 [SDOI2005] 區間 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)https://www.luogu.com.cn/problem/P2434

?

1. 思路分析

給出若干個區間讓我們輸出它們可以合并出來最少的區間（個數，但是輸出區間）。

1.按照左端點排序

2.排序完了以后定義兩個變量L和R,L=第一個區間的左端點,R=第一個區間的右端點

3.遍歷一遍這些區間(不包含第一個)

4.如果這個區間的左端點(開端),大于了R(這個區間不在我們L~R里不包含它),輸出L和R,把L的值更新為這個區間的左端點（更新一下整個區間）

5. R的值和區間的右端點做比較選取最大的那個值更新R

2.上代碼

#include <bits/stdc++.h>
using namespace std;
struct B{int l,r;
}a[1000005];
bool cmp(B x, B y){return x.l < y.l;
}
int main(){int n;cin >> n;for (int i = 0; i < n; i++){cin >> a[i].l >> a[i].r;}sort(a,a+n,cmp);int R = a[0].r,L = a[0].l;for (int i=1; i <n ; i++){if (a[i].l > R){cout << L << " " << R << "\n";L = a[i].l;}R = max(a[i].r,R);}cout << L << " " << R << "\n";return 0;
}

4.區間覆蓋問題

?P1668 [USACO04DEC] Cleaning Shifts S

?P1668 [USACO04DEC] Cleaning Shifts S - 洛谷 | 計算機科學教育新生態 (luogu.com.cn)https://www.luogu.com.cn/problem/P1668

這道題題目的意思是：給定我們一個區間1~T,我們有N個小區間,請問需要最少幾個小區間可以覆蓋整個大區間(1~T),請注意兩個區間之間可以差一，只要每個時間段都有奶牛也可以，比如（1，2）（3，4）它們就可以并到一起去。雖然它講起來是時間段但是它做起來是時間點。

1.思路分析

圖片分析請看下圖

?2.代碼解釋

#include <bits/stdc++.h>
using namespace std;
struct Sa{int a,b;
}s[100005];
bool cmp(Sa x,Sa y){return x.a < y.a;
}
int main(){int n,t;cin >> n >> t;int cnt=0;for (int i= 1; i <= n; i++){cin >> s[i].a >> s[i].b;}sort(s+1,s+n+1,cmp);

結構體函數+排序函數cmp按照左端點從小到大排+輸入與排序

int l = 1,r = -1;for (int i = 1; i <= n;){if (s[i].a > l){cout <<-1;return 0;}

如果左端點最靠前的那個區間,左端點還是大于L,說明整個區間結構體沒有一個左端點小于等于L,輸出負一不能實現

while (i <= n and s[i].a <= l){r = max(s[i].b,r);i++;}cnt ++;

去看,左端點小于等于,而且右端點是最大的.增加區間段數(cnt).

if (r >= t){cout << cnt;return 0;}l = r +1;}

如果我們的最大值已經超過了T輸出cnt,把L更新為r+1.

cout << -1;return 0;
}

對如果在循環里都沒結束的話,說明不可以實現輸出-1

?總體代碼

#include <bits/stdc++.h>
using namespace std;
struct Sa{int a,b;
}s[100005];
bool cmp(Sa x,Sa y){return x.a < y.a;
}
int main(){int n,t;cin >> n >> t;int cnt=0;for (int i= 1; i <= n; i++){cin >> s[i].a >> s[i].b;}sort(s+1,s+n+1,cmp);int l = 1,r = -1;for (int i = 1; i <= n;){if (s[i].a > l){cout <<-1;return 0;}while (i <= n and s[i].a <= l){r = max(s[i].b,r);i++;}cnt ++;if (r >= t){cout << cnt;return 0;}l = r +1;}cout << -1;return 0;
}

5.區間分組

呃……，這道題你們就看圖片吧！

T471772 cici排課

?1.一點點思路

這個題目不在于老師的編號是多少哪個老師該上哪節課，只用求出老師的個數就行。

只要有課程下課了的話我們就可以釋放老師,如果釋放了新課,既要把新課排給被釋放的老師.

2.代碼實現與算法思路

#思路

我們輸給兩個數組(a,b),注意在這里不要用區間的眼光看這兩個數組, 數組要分開來排序, a從小到大排序b也從小到大排序,定義一個變量cnt(老師數量)然后循環:

a的i號位的數與b的第j號位對比,如果小于等于B的第j號位{

????????cnt++

????????查看a的i+1號位//也就是i++;

}//這個循環也就是循環到a[i]>b[j],看一看在b[j]這個課結束之前,還會上多少節課

如果b[j]比a[i]為小的話{//也就是說有老師被釋放出來了

? ? ? ? cnt --

? ? ? ? j++;//看下一位

}

#代碼實現，增加一些判斷我會進行注釋?

為什么要求最大值，因為這種方法是最值的，而求最大值是要求這種最值方法需要多少名老師

#include <bits/stdc++.h>
using namespace std;
int a[100005],b[100005];
int main(){int n;cin >> n;for (int i =0; i < n; i++){cin >> a[i] >> b[i];}sort(a,a+n);sort(b,b+n);int i = 0,j = 0,big = -1,cnt = 0;while (1){while (i < n and a[i] <= b[j]){cnt ++;big = max(cnt,big);//求最大值i ++;}if (i >= n) break;  //如果要上的課都檢查完了就退出輸出最大值while (j < n and b[j] < a[i]){cnt --;j ++;}}cout << big;return 0;
}

3.舉一反三

這道題會讓我們想起“匹配括號”，雖然不知道這個題名字叫做什么，但是題目的大致意思如下：

輸入一個字符串字符串用“（”和“）”組成，“（”和“）”可以形成一組，請問輸入的字符串有沒有多余的括號。如果沒有輸出“yes”如果有輸出“no”（不加引號）。

就比如輸入：

（（（））（））

很明顯是匹配上了的

請看下列表格是我們這道題的算法，左括號加一，右括號減一

（	（	（	）	）	（	）	）
1	2	3	2	1	2	1	0

如果最后等于零的話就可以匹配成功.

不過你可能會問這道題和cici排課有什么關系 ,你可以把題目改編一下變成:

還是輸入一個字符串,每一個符號(左括號、右括號)之間，輸出我們的cnt最大值。

我們借鑒上面的表格,這個題目就可以輸出3

而我們的CiCi排課也是同樣的道理,左括號是開始上課,右括號是結束上課,問你老師人數的最大值.

3.遇到了(區間)貪心的題我們應該怎么做

找出我們要排序的順序按什么排序,

再進行循環,加入題目的要求

最后說一句特殊題目特殊判斷,一定要變得靈活起來.

end👍🏻?