貪心算法：

在對問題求解的時候，總是做出在當前看來最好的選擇，

也就是說不從整體上進行考慮，它所做出的僅僅是在某種意義上的局部最優解
是否是全優解，需要證明。
若用貪心算法求解某問題的整體最優解，
必須證明貪心思想在該問題的應用結果就是最優解

貪心：每次都選看起來最好的！

例一：

有n個人在一個水龍頭前排隊接水，假如每個人接水的時間為Ti，

請編程找出這n個人排隊的一種順序，使得n個人的平均等待時間最小。

貪心策略：

第1個人的等待時間為0，第二個人的等待的時間為t[1],第三個人的等待時間為t[1]+t[2]

第n個人的等待時間為前n-1個人接水的時間之和，所以將n個人的接水時間從小到大排序

這就是n個人排隊的順序，使得n個人的平均等待時間最小

#include<bits/stdc++.h> using namespace std; const int MAX=1e5+5; int t[MAX],n; int main() {while(cin>>n){for(int i=0;i<n;i++)cin>>t[i];sort(t,t+n);int sum=0;for(int i=1;i<n;i++)t[i]+=t[i-1];for(int i=0;i<n;i++)sum+=t[i];cout<<sum<<endl;}return 0; }

例二：

銀行排隊

時間限制:?1 Sec??內存限制:?128 MB
提交:?299??解決:?115
[提交][狀態][討論版]

題目描述

有n個人將要排隊在銀行辦理業務，已知每個人辦理業務所花費的時間，分別是t1,t2,t3...tn。現在，你可以重新安排他們的排隊順序，目的是為了使所有人從排隊開始到業務辦理完成花費的時間總和最少?，F在你只需要告訴我，安排好后所有人花費的時間總和最少是多少？

輸入

本題有多組測試數據。每組數據第一行給出一個正整數n，代表有n個人排隊，其中n<=100。接下來一行有n個正整數，分別代表這每個人辦理業務所需要花費的時間。

輸出

對每個測試用例，在每一行里輸出所有人花費時間的總和最少的值。

樣例輸入

5 3 1 2 2 1 10 2 1 3 1 3 4 5 8 7 4

樣例輸出

22 147
#include<stdio.h> #include<algorithm> using namespace std;int tim[101]; int main() {int N;while(scanf("%d",&N)!=EOF){for(int i=0;i<N;i++)scanf("%d",&tim[i]);sort(tim,tim+N);int ans=0,sum;for(int i=0;i<N;i++){sum=0;for(int j=0;j<=i;j++){sum +=tim[j];}ans+=sum;} printf("%d\n",ans);}return 0; }

例三：

水題

Time Limit: 500 MS Memory Limit: 32768 K Total Submit: 428(149 users) Total Accepted: 164(109 users) Rating:? Special Judge:?No

Description

因為是有關于接水的問題，便簡稱為水題了（。 N個人排隊在M個出水口前接水，第i個人接水需時為t[i]， 請問接水的最短用時是多少？

Input

第一行一個整數?T?，代表有?T?組數據。 每組數據 第一行兩個整數?N(<=100000) , M(<=10000)?代表有?N?個人?M?個出水口。 第二行N個整數，第i個數字t[i](<=10000)代表第i個人接水用時t[i]。

Output

對于每組數據輸出一個整數，代表所需的最少接水時間。

Sample Input

2 5 3 1 2 3 4 5 6 3 1 2 3 3 4 5

Sample Output

5 6

Hint

小橋流水嘩啦啦，我和小島去偷瓜~。

Source

"誠德軟件杯"哈爾濱理工大學第四屆ACM程序設計團隊賽

點擊打開鏈接

貪心 + 二叉推

將所有人從大到小排序，依次插入 M 個出水口， 每次要插入到用時最少的出水口，最后輸出 M個出水口中用時最多的

#include<stdio.h> #include<vector> #include<iostream> #include<queue> #include<algorithm> using namespace std;int cmp(int a,int b) {return a>b; } int tim[101000]; int main() {int T,N,M;cin>>T;while(T--){cin>>N>>M;priority_queue<int,vector<int>,greater<int> >pq;//優先隊列，從小到大入隊列//將 M 個出水口用時初始化為 0for(int i=0;i<M;i++)pq.push(0);for(int i=0;i<N;i++)cin>>tim[i];sort(tim,tim+N,cmp);//從大到小排序for(int i=0;i<N;i++){int temp=pq.top();//每次取出時間最小的出水口pq.pop();//出隊列temp+=tim[i];//將第 i 個人插入到目前時間最小的出水口 pq.push(temp);} int ans=-1;//遍歷循環，找出最大值 while(!pq.empty()){if(ans<pq.top())ans=pq.top();pq.pop(); }printf("%d\n",ans);}return 0; }

例四：點擊打開鏈接

合并果子

現在有n堆果子，第i堆有ai個果子?，F在要把這些果子合并成一堆，每次合并的代價是兩堆果子的總果子數。求合并所有果子的最小代價。

Input

第一行包含一個整數T（T<=50），表示數據組數。
每組數據第一行包含一個整數n（2<=n<=1000），表示果子的堆數。
第二行包含n個正整數ai（ai<=100），表示每堆果子的果子數。

Output

每組數據僅一行，表示最小合并代價。

Sample Input 2 4 1 2 3 4 5 3 5 2 1 4Sample Output 19 33

優先隊列

#include<iostream> #include<queue> //#include<bits/stdc++.h> using namespace std; const int MAX=1e4+5; int n; int main() {ios::sync_with_stdio(false);int t;cin>>t;while(t--){int n,x;cin>>n;priority_queue<int,vector<int>,greater<int> >q;for(int i=0;i<n;i++){cin>>x;q.push(x);}long long sum=0;while(q.size()>1){int min1=q.top();q.pop();int min2=q.top();q.pop();sum+=(min1+min2);q.push(min1+min2);}cout<<sum<<endl;} return 0;}

STL堆算法

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() {int t;cin>>t;while(t--){int n;cin>>n;vector<int> v;while(n--){int x;cin>>x;v.push_back(x);}long long sum=0;make_heap(v.begin(),v.end(),greater<int>());while(v.size()>1){int min1=v.front();pop_heap(v.begin(),v.end(),greater<int>());v.pop_back();int min2=v.front();pop_heap(v.begin(),v.end(),greater<int>());v.pop_back();//cout<<min1<<" "<<min2<<endl;sum+=(min1+min2);v.push_back(min1+min2);push_heap(v.begin(),v.end(),greater<int>());}cout<<sum<<endl;}return 0; }

例５：

n個正整數，聯接成一排，組成一個最小（最大）的多位整數

描述：設有n個正整數，將它們聯接成一排，組成一個最小（最大）的多位整數。

程序輸入：n個數程序輸出：聯接成的多位數例如：n=2時，2個整數32、321連接成的最小整數為：32132

n=3時，3個整數13,312,343,連成的最大整數為34331213。
n=4時,4個整數7,13,4,246連接成的最大整數為7424613。

n=4時，4個整數55、31、312、33 聯接成的最小整數為：312313355

思路：兩個方向:a.先組合，后排序，b.先排序，后組合，但是要注意：A=’321’，B=’32’，

按照標準的字符串比較規則因為A>B，所以A+B > B+A ，而實際上’32132’ < ’32321’。?

所以，自定義一種字符串的比較規則：即如果A+B>B+A,則我們認為A>B。

#include<bits/stdc++.h> using namespace std; bool cmp(string a,string b) {return a+b>b+a; } int main() {ios::sync_with_stdio(false);string s;vector<string> v;int n;cin>>n;for(int i=0;i<n;i++){cin>>s;v.push_back(s);}sort(v.begin(),v.end(),cmp);for(int i=0;i<v.size();i++)cout<<v[i];cout<<endl;return 0;}

例６

事件序列問題?

已知N個事件的發生時刻和結束時刻（見下表，表中事件已按結束時刻升序排序）。

一些在時間上沒有重疊的事件，可以構成一個事件序列，如事件{2，8，10}。

事件序列包含的事件數目，稱為該事件序列的長度。請編程找出一個最長的事件序列。

算法分析：

用begin[i],end[i]表示事件i的開始時刻和結束時刻，
則問題轉化為求 a1<a2<a3<...<an 滿足：
begin[a1]<end[a1] <= begin[a2]<end[a2] <= begin[an]<end[an]

hdu 2037

#include <stdio.h> #include <algorithm> using namespace std; struct node { int t1;//電視開始時間 int t2;//電視的結束時間 }a[105]; int cmp(node u,node v) //對節目按照結束時間從小到大排序， //如果結束的時間相同，則按照開始的 {//時間從大到小的排序！ if(u.t2==v.t2)//為什么要將開始的時間從大到小排序呢？//是因為如果結束時間相同的話，開始的 //越遲，看節目的時間越短，你就能盡可能的多看電視！ return u.t1>v.t1;return u.t2<v.t2;//例如：2-3,3-4,2-4，你肯定會看2-3,3-4的兩個電視，而不看2-4這個電視 } int main() { int n,i,j,k,t; while(scanf("%d",&n)&&n) { for(i=0;i<n;i++)//有n個開始和結束時間，將時間輸入 scanf("%d%d",&a[i].t1,&a[i].t2); sort(a,a+n,cmp);//對時間進行排序 for(i=1,t=a[0].t2,k=1;i<n;i++)//如果開始 的時間比他這個結束的時間遲，則就k++ { if(a[i].t1>=t)//說明這個電視你能夠看 { t=a[i].t2; k++; } } printf("%d\n",k);//k代表能看的電視的個數！ } return 0; }

例7：

HDU 4221 貪心

題意：

給n個活動，每個活動需要一段時間C來完成，并且有一個截止時間D，
當完成時間t大于截止時間完成時，會扣除t-D分，
讓你找出如何使自己所扣分的最大值最小。

注意：求得是沒有按時完成的任務罰金最多的那個!

思路：按照截止時間從小到大來排序，從第一天開始做任務，每個任務的完成時間減去截止時間相對來說最少

#include<iostream> #include<algorithm> using namespace std; const int MAX=1e6+5; struct node{int c,d; }a[MAX]; bool cmp(node a,node b) {return a.d<b.d; } int main() {ios::sync_with_stdio(0);int t,T=1;cin>>t;while(t--){int n;cin>>n;for(int i=0;i<n;i++)cin>>a[i].c>>a[i].d;sort(a,a+n,cmp);long long ans=0,time=0;for(int i=0;i<n;i++){time+=a[i].c;if(ans<time-a[i].d){ ans=time-a[i].d;}}printf("Case %d: %I64d\n",T++,ans);}return 0; }

例8：

NOIP2012 國王游戲 題解

描述

恰逢H國國慶，國王邀請n位大臣來玩一個有獎游戲。首先，他讓每個大臣在左、右手上面分別寫下一個整數，國王自己也在左、右手上各寫一個整數。然后，讓這n位大臣排成一排，國王站在隊伍的最前面。排好隊后，所有的大臣都會獲得國王獎賞的若干金幣，每位大臣獲得的金幣數分別是：排在該大臣前面的所有人的左手上的數的乘積除以他自己右手上的數，然后向下取整得到的結果。?
國王不希望某一個大臣獲得特別多的獎賞，所以他想請你幫他重新安排一下隊伍的順序，使得獲得獎賞最多的大臣，所獲獎賞盡可能的少。注意，國王的位置始終在隊伍的最前面。

格式

輸入格式

第一行包含一個整數n，表示大臣的人數。?
第二行包含兩個整數a和b，之間用一個空格隔開，分別表示國王左手和右手上的整數。接下來n行，每行包含兩個整數a和b，之間用一個空格隔開，分別表示每個大臣左手和右手上的整數。

輸出格式

輸出只有一行，包含一個整數，表示重新排列后的隊伍中獲獎賞最多的大臣所獲得的金幣數。

樣例1

樣例輸入1[復制]

3 1 1 2 3 7 4 4 6

樣例輸出1[復制]

2

限制

每個測試點1s

提示

對于20%的數據，有1≤ n≤ 10，0 < a、b < 8；?
對于40%的數據，有1≤ n≤20，0 < a、b < 8；?
對于60%的數據，有1≤ n≤100；?
對于60%的數據，保證答案不超過10^9；?
對于100%的數據，有1 ≤ n ≤1,000，0 < a、b < 10000。

【題解】

? 一開始看著題覺得是二分答案（最大值的最小值），后來發現不滿足單調性

? 再后來發現可以用貪心做：只需把大臣按照左手*右手升序排序即可

? 證明：

? ?很顯然前面的大臣位置隨便調換對后面的大臣并沒有影響

? 那么假設現在已經排了i-1個大臣,p=a[1]*a[2]*a[3]*……*a[i-1];

? 第i個大臣的錢w[i]=p/b[i],第i+1個大臣的錢w[i+1]=p*a[i]/b[i+1]

? 若i+1大臣在i大臣前面

??第i個大臣的錢w[i]=p*a[i+1]/b[i],第i+1個大臣的錢w[i+1]=p/b[i+1]

? 顯然p*a[i+1]/b[i]>p/b[i] ?&& ?p*a[i]/b[i+1]>p/b[i+1]

? 所以兩個里面的最大值在p*a[i+1]/b[i] 和 p*a[i]/b[i+1] 之間 ?

? 若p*a[i+1]/b[i] > p*a[i]/b[i+1]（這樣就是i+1大臣排在i后面最大值會更小） 則 a[i+1]*b[i+1]>a[i]*b[i]

? 所以如果要讓大臣得到的錢的最大值最小就要保證兩個相鄰的大臣，前面的左手*右手<后面的左手*右手

#include<bits/stdc++.h> using namespace std; const int MAX=1e4+5; struct node{int right,left,m; }a[MAX]; bool cmp(node a,node b){if(a.m==b.m)return a.right<b.right;return a.m<b.m; } long long num=1,ans=0; int main() {ios::sync_with_stdio(false);int n;cin>>n;for(int i=0;i<=n;i++){cin>>a[i].left>>a[i].right;a[i].m=a[i].left*a[i].right;}sort(a+1,a+1+n,cmp);for(int i=0;i<=n;i++){ans=max(ans,num/a[i].right);num*=a[i].left;}printf("%I64d\n",ans);return 0;}

總結

以上是生活随笔為你收集整理的算法竞赛入门与进阶 （三）贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。