算法筆記（5）貪心算法
原發(fā)表于我的博客
貪心算法
貪心與其說是一種算法，不如說一種思想。
貪心思想，顧名思義，就是總是做出當前最好的選擇，這種方式可能在全局上不是最好的結果，但是在一些題目中就可以直接用。
最簡單的例子就是“貨比三家”，在生活中，我們買東西時都會挑性價比最優(yōu)的，這就是一種貪心。
貪心算法在OI中經(jīng)常與其他算法或數(shù)據(jù)結構結合到一起，有些題目比較考驗思維能力。
貪心算法一般會用到的算法或數(shù)據(jù)結構不多，一般的題目只需要用到排序，有些題目可以用優(yōu)先隊列動態(tài)維護最值。
接下來我們介紹幾種貪心算法的“套路”。
取最優(yōu)
最經(jīng)典的問題就是最優(yōu)裝載問題。
商店里有\(n\)個物品，每個物品給出價值和重量，現(xiàn)在來了個小偷，小偷只能帶走\(m\)千克的物品，問他最多能帶走多少錢的物品。
對于這道題，我們可以直接算出每一個物品的性價比，然后對于性價比排序，依次累加，直到重量超過\(m\)為止。
代碼
struct node{
int w,m;//價值和重量
double d;//性價比
}a[N];
bool cmp(node a,node b){
return a.d>b.d;//按照性價比從小到大排序
}
int n,m;
int main(){
cin>>n>>m;//n個物品，限定m重量
for(int i=1;i<=n;i++) cin>>a[i].w>>a[i].m,a[i].d=(double)a[i].w/(double)a[i].m;
sort(a+1,a+1+n,cmp);//排序
int s1=0,s2=0;//分別為價值的累計和重量的累計
for(int i=1;i<=n;i++){
s1+=a[i].w,s2+=a[i].m;
if(s2+a[i+1].m>m) break;//如果超出m限制，就退出
}
cout<<s1;//輸出累計價格
}
不相交區(qū)間問題
在一個數(shù)軸上有n條線段，現(xiàn)要選取其中k條線段使得這k條線段兩兩沒有重合部分,問最大的k為多少?
關于這題的貪心策略，我們可以按每個區(qū)間的右端點排序，然后每個區(qū)間判斷一下是否與前面的區(qū)間重合，累加答案即可。
代碼
struct node{
int l,r;//結構體
};
vector<node>v;
int n,ans=0;
bool cmp(node a,node b){
return a.r<b.r;//按右端點排序
}
int main(){
cin>>n;
while(n--){
int l,r;
cin>>l>>r;
v.push_back({l,r});//使用vector容器
}
sort(v.begin(),v.end(),cmp);
int l=v.front().l;//初始l為第一個區(qū)間的左端點
for(auto it:v){
if(it.l>=l){//如果不重合，就累加答案
ans++;
l=it.r;//更新l指針
}
}
cout<<ans;
}
區(qū)間選點問題
給定\(N\)個區(qū)間\([a,b]\)，取盡量少的點，使得每個區(qū)間內(nèi)都至少有一個點（不同區(qū)間內(nèi)含的點可以重復）。
如何能選取更少的點呢？
如果在幾個區(qū)間的重疊部分放點，那么就會覆蓋多個區(qū)間，就會少取一些點。
如圖，如果兩個區(qū)間有重疊部分，那么前面區(qū)間的右端點肯定在重疊部分里。
所以我們可以選擇在每個區(qū)間的右端點放點，這樣就會覆蓋更少的區(qū)間。
所以我們的貪心策略就是：首先按區(qū)間的結束位置從小到大排序。然后從區(qū)間\(1\)到區(qū)間\(n\)進行選擇；對于當前區(qū)間，若集合中的數(shù)不能覆蓋它，則將區(qū)間末尾的數(shù)加入集合。
代碼
int vis[N];
struct node{
int u,v,w;
}a[N];
int m,h,ans=0;
int cmp(node a,node b){
return a.v<b.v;//按照右端點排序
}
int main(){
cin>>m>>h;
for(int i=1;i<=h;i++) cin>>a[i].u>>a[i].v>>a[i].w;
sort(a+1,a+1+h,cmp);//排序
for(int i=1;i<=h;i++){
int cnt=0;
for(int j=a[i].u;j<=a[i].v;j++) cnt+=vis[j];
if(cnt>=a[i].w) continue;
for(int j=a[i].v;j>=a[i].u,cnt<a[i].w;j--){
if(!vis[j]) cnt++,vis[j]++,ans++;
}
}
cout<<ans;
}
中位數(shù)
在貪心算法中，中位數(shù)是一個比較神奇的性質(zhì)。
我們以經(jīng)典的貨倉選址問題為例。
在一條數(shù)軸上有 \(N\) 家商店，它們的坐標分別為 \(A_1～A_N\)。現(xiàn)在需要在數(shù)軸上建立一家貨倉，每天清晨，從貨倉到每家商店都要運送一車商品。求把貨倉建在何處，可以使得貨倉到每家商店的距離之和最小。
可以證明，當選取中位數(shù)時，距離之和最小。
代碼
int a[N],sum,n;
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
sort(a+1,a+n+1);
int mid=a[n/2];
for(int i=1;i<=n;i++) sum+=abs(a[i]-mid);
cout<<sum<<endl;
}
與優(yōu)先隊列相結合
很多貪心題目可以和堆結合到一起，在平時做題時，可以使用stl中的優(yōu)先隊列priority_queue。
合并果子是一道比較經(jīng)典的優(yōu)先隊列優(yōu)化貪心題。
有\(n\)個果子，每次可以任意選擇兩個進行合并，每次合并耗費的體力值是兩個果子重量之和，問最小耗費體力值。
因為是任意兩個進行合并，所以我們可以每次選擇果子里面重量最小的兩個果子合并。
但是暴力找重量最小的果子復雜度為\(O(n)\)，總體\(O(n^2)\)的時間復雜度不能接受。考慮用數(shù)據(jù)結構優(yōu)化。
什么數(shù)據(jù)結構能支持動態(tài)找最小值呢？堆！
在這里我們可以使用stl中的優(yōu)先隊列，這樣就有了\(O(n\log n)\)的復雜度。
代碼
#include<bits/stdc++.h>
using namespace std;
priority_queue<int,vector<int>,greater<int>>q;//優(yōu)先隊列
int n,ans=0;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int t;
cin>>t;
q.push(t);//在優(yōu)先隊列中加入所有果子
}
while(!q.empty()){
int t1=q.top();//取出當前重量最小的果子
q.pop();
if(q.empty()) break;
int t2=q.top();
q.pop();
ans+=t1+t2,q.push(t1+t2);
}
cout<<ans;
}
反悔貪心
沒人看的，所以咕了
例題
一本通提高篇的幾道貪心水題。
【一本通提高篇貪心】 活動安排
題目大意
選取最多的區(qū)間，使它們沒有重疊部分。
貪心思路
按照活動的結束時間進行升序排序，因為一個活動結束的越早，就越不容易與其他活動起沖突。
這題就是上面寫到的不相交區(qū)間問題，這里就不仔細講了，直接看代碼。
AC代碼
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
struct node{
int l,r;//結構體
};
vector<node>v;
int n,ans=0;
bool cmp(node a,node b){
return a.r<b.r;//按右端點排序
}
int main(){
cin>>n;
while(n--){
int l,r;
cin>>l>>r;
v.push_back({l,r});//使用vector容器
}
sort(v.begin(),v.end(),cmp);
int l=v.front().l;//初始l為第一個區(qū)間的左端點
for(auto it:v){
if(it.l>=l){//如果不重合，就累加答案
ans++;
l=it.r;//更新l指針
}
}
cout<<ans;
}
【一本通提高篇貪心】 種樹
題目大意
即剛剛講過的區(qū)間選點問題。
貪心思路
按每個路段的右端點排序，枚舉每一個路段，從左端點枚舉到右端點。
因為如果右端點重疊了，就少種了一棵樹，所以只要這個位置有樹，這個路段要求的樹的數(shù)量就-1。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=3e4+10;
int vis[N];
struct node{
int u,v,w;
}a[N];
int m,h,ans=0;
int cmp(node a,node b){
return a.v<b.v;
}
int main(){
cin>>m>>h;
for(int i=1;i<=h;i++) cin>>a[i].u>>a[i].v>>a[i].w;
sort(a+1,a+1+h,cmp);
for(int i=1;i<=h;i++){
int cnt=0;
for(int j=a[i].u;j<=a[i].v;j++) cnt+=vis[j];
if(cnt>=a[i].w) continue;
for(int j=a[i].v;j>=a[i].u,cnt<a[i].w;j--){
if(!vis[j]) cnt++,vis[j]++,ans++;
}
}
cout<<ans;
}
【一本通提高篇貪心】 噴水裝置
題目大意
有 \(n\) 個澆灌噴頭。每個噴頭都裝在草坪中心線上（離兩邊各\(\frac{W}{2}\)米）。我們知道每個噴頭的位置（離草坪中心線左端的距離），以及它能覆蓋到的澆灌范圍。
請問：如果要同時澆灌整塊草坪，最少需要打開多少個噴頭？
貪心思路
這題怎么這么計幾?。?/s>
如圖，每個噴水裝置覆蓋的區(qū)域不是它的直徑，我們需要用勾股定理算出那個圓和那個方塊的交集的距離，即\(\sqrt{r^2-(\frac{w}{2})^2}\)。
算出這個距離后，就是一道裸的區(qū)間覆蓋問題了。
所以我們的貪心思路就是，先處理處每一個區(qū)間的左右端點（即\(x-\sqrt{r^2-(\frac{w}{2})^2}\)和\(x+\sqrt{r^2-(\frac{w}{2})^2}\)），然后按左端點排序，依次處理即可，細節(jié)部分看代碼。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=15010;
int T,n,m;
double l,w;
struct node{
double l,r;
}a[N];
bool cmp(node a,node b){
return a.l<b.l;
}
void work(){
m=0;
cin>>n>>l>>w;
for(int i=1;i<=n;i++){
double id,r;
cin>>id>>r;
if(r<=w/2) continue;
double d=sqrt(r*r-w*w/4.0);
a[++m]={id-d,id+d};
}
sort(a+1,a+1+m,cmp);
double now=0;
int cnt=0,i=1;
while(now<l){
cnt++;
double tmp=now;
while(a[i].l<=tmp&&i<=m) now=max(now,a[i].r),i++;
if(tmp==now&&tmp<l){
cout<<-1<<endl;
return;
}
}
cout<<cnt<<endl;
}
int main(){
cin>>T;
while(T--) work();
return 0;
}
【一本通提高篇貪心】 加工生產(chǎn)調(diào)度
題目大意
有\(n\)個物品需要加工，每個物品先在\(A\)車間加工再到\(B\)加工，問最短加工時間。
貪心策略
按每個物品在\(A\)和\(B\)車間的加工時間的最小值排序，然后模擬即可。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n;
struct node{
int a,b,id;
}a[N];
int w[N];
bool cmp2(node a,node b){
return min(a.a,b.b)<min(a.b,b.a);
}
bool cmp1(node a,node b){
return min(a.a,a.b)<min(b.a,b.b);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i].a,a[i].id=i;
for(int i=1;i<=n;i++) cin>>a[i].b;
sort(a+1,a+1+n,cmp1);
for(int i=1,l=0,r=n+1;i<=n;i++){
if(a[i].a<a[i].b) w[++l]=a[i].id;
else w[--r]=a[i].id;
}
int s1=0,s2=0;
sort(a+1,a+1+n,cmp2);
for(int i=1;i<=n;i++){
s1+=a[i].a;
s2=max(s1,s2);
s2+=a[i].b;
}
cout<<s2<<endl;
for(int i=1;i<=n;i++) cout<<w[i]<<" ";
}
【一本通提高篇貪心】 智力大沖浪
題目大意
有一些任務，每個任務都有完成期限，完不成一個任務就要扣一些錢，問最多能得到多少錢。
貪心策略
直覺上，如果要扣錢最少，肯定得讓扣錢多的排到前面去，然后按照時間依次完成任務。
但是這樣做是錯誤的（通過樣例就能得出結論），所以我們需要優(yōu)化一下這個思路。
我們可以用最優(yōu)貪心，每個任務都在完成期限的最后一秒完成，用一個數(shù)組記錄下每個時間點有沒有被一個任務占用，然后向前找到最后一個能用的時間即可。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=510;
struct node{
int t,x;
}a[N];
bool cmp(node a,node b){
return a.x>b.x;
}
int n,m,tim[N];
int main(){
cin>>m>>n;
for(int i=1;i<=n;i++) cin>>a[i].t;
for(int i=1;i<=n;i++) cin>>a[i].x;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
for(int j=a[i].t;j;j--){
if(!tim[j]){
tim[j]=1,a[i].x=0;
break;
}
}
}
for(int i=1;i<=n;i++) m-=a[i].x;
cout<<m;
}
【一本通提高篇貪心】 數(shù)列極差
題目大意
有\(n\)個正整數(shù)，每次刪去兩個數(shù)\(a,b\)，放入一個數(shù)\(a\times b+1\)，問最后得到的一個數(shù)的最大值和最小值。
貪心策略
我們會發(fā)現(xiàn)這題很像之前的例題果子合并，所以我們可以考慮用堆維護。
而我們要同時維護最大值和最小值，可以用一個大根堆和一個小根堆。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=20;
priority_queue<int,vector<int>,greater<int>>a;//大根堆
priority_queue<int,vector<int>,less<int>>b;//小根堆
int n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
int t;
cin>>t;
a.push(t),b.push(t);//分別加入兩個中
}
//分別進行兩個堆的維護過程，具體過程很像果子合并
while(a.size()>1){
int tmp=a.top();
a.pop();
tmp*=a.top();
a.pop();
a.push(tmp+1);
}
while(b.size()>1){
int tmp=b.top();
b.pop();
tmp*=b.top();
b.pop();
b.push(tmp+1);
}
cout<<a.top()-b.top();//輸出題目要求維護的極差
}
【一本通提高篇貪心】 數(shù)列分段
題目大意
給定的一個正整數(shù)數(shù)列 ，現(xiàn)要將其分成連續(xù)的若干段，并且每段和不超過\(m\)，問最少分成幾段。
貪心策略
這題就是最簡單的貪心了，枚舉的過程中累加和，如果超過\(m\)就情況，然后段數(shù)\(+1\)，沒有什么思維含量。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int t,n,m,s=0,cnt=0;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>t;
if(s+t>m) s=0,cnt++;
s+=t;
}
cout<<cnt+1;
}
【一本通提高篇貪心】 線段
題目大意
在一個數(shù)軸上有\(n\)條線段，現(xiàn)要選取其中\(k\)條線段使得這\(k\)條線段兩兩沒有重合部分,問最大的\(k\)為多少?
貪心策略
即不相交區(qū)間問題，和習題第一道幾乎一模一樣，這里直接上代碼。
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
int l,r;
}a[N];
bool cmp(node a,node b){
return a.r<b.r;
}
int n,k=0;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) cin>>a[i].l>>a[i].r;
sort(a+1,a+1+n,cmp);
int t=0;
for(int i=1;i<=n;i++){
if(a[i].l>=t) t=a[i].r,k++;
}
cout<<k;
}
【一本通提高篇貪心】 家庭作業(yè)
題目大意
有一些作業(yè)，每個作業(yè)有完成期限，每個作業(yè)完成會得到一定的學分，問最多能得到多少學分。
貪心策略
我們會發(fā)現(xiàn)這道題和智力大沖浪那題很像，但是那題做法的時間復雜度是\(O(n^2)\)，但這題的數(shù)據(jù)范圍是\(10^6\)，所以需要優(yōu)化。
一種優(yōu)化方式是用并查集優(yōu)化，并查集數(shù)組記錄下最遠能夠追溯到的放置時間，如果用路徑壓縮優(yōu)化的話，時間復雜度可以達到\(O(\alpha n)\)，其中\(\alpha \le5\)
AC代碼
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
int t,x;
}a[N];
bool cmp(node a,node b){
return a.x>b.x;
}
int n,m,tim[N],fa[N],ans=0;
int find(int x){
//并查集查詢
if(x==fa[x]) return x;//路徑壓縮
return fa[x]=find(fa[x]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].t>>a[i].x;
m=max(m,a[i].t);
}
for(int i=0;i<=m;i++) fa[i]=i;//初始化并查集
sort(a+1,a+1+n,cmp);
for(int i=1;i<=n;i++){
int d=find(a[i].t);
if(d) fa[d]=d-1,ans+=a[i].x;
}
cout<<ans;
}
【一本通提高篇貪心】 糖果傳遞
題目大意
有\(n\)個小朋友坐成一圈，每人有\(a_i\)個糖果。每人只能給左右兩人傳遞糖果。每人每次傳遞一個糖果代價為\(1\)。求使所有人獲得均等糖果的最小代價。
貪心策略
本題需要一定的數(shù)學推導，比較繁瑣，這里暫時略過，讀者可以去找網(wǎng)上的題解。
AC代碼
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int n,a[N],s[N],sum=0;
signed main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],sum+=a[i];
for(int i=2;i<=n;i++){
s[i]=s[i-1]+a[i]-sum/n;
}
sort(s+1,s+1+n);
int mid=s[n/2+1],ans=0;
for(int i=1;i<=n;i++) ans+=abs(s[i]-mid);
cout<<ans;
}
浙公網(wǎng)安備 33010602011771號