贪心算法
一、贪心算法
贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择。也就是说，不从整体最优上加以考虑，做出的只是在某种意义上的局部最优解
二、例题
例题一、区间问题
问题描述：
有n项工作，每项工作分别在si开始，ti结束。对每项工作，你都可以选择参加或不参加，但选择了参加某项工作就必须至始至终参加全程参与，即参与工作的时间段不能有重叠(即使开始的时间和结束的时间重叠都不行)。
限制条件：
1<=n<=100000
1<=si<=ti,=109
样例：
输入
5
1 2 4 6 8
3 5 7 9 10
输出
3(选择工作1, 3, 5)
题解：有三种算法：一是挑选开始时间最早的方案，二是挑选重叠次数最少的方案，三是结束时间最早的方案。经选择，选择方案三
代码：
#include<iostream>
#include<algorithm>
#include<string>
#include<utility>
#define maxn 100005
using namespace std;
typedef pair<int,int> P;
int N,endtime[maxn],starttime[maxn];
P pai[maxn];
int tanxin()
{
for(int i=0;i<N;i++)
{
pai[i].first=endtime[i];
pai[i].second=starttime[i];
}
sort(pai,pai+N);//默认先对first排序，再对second排序
int t=pai[0].first;
int ans=1;
for(int i=0;i<N;i++)
{
if(t<pai[i].second)
{
t=pai[i].first;
ans++;
}
}
return ans;
}
int main()
{
while(cin>>N)
{
for(int i=0;i<N;i++)
cin>>starttime[i];
for(int i=0;i<N;i++)
cin>>endtime[i];
int ans=tanxin();
cout<<ans<<endl;
}
return 0;
}
例题二、分饼干
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i ，都有一个胃口值 gi ，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j ，都有一个尺寸 sj 。如果 sj >= gi ，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值
样例
输入:3 2
1 2 3
1 1
输出: 1
题解：本题采用贪心策略。将饼干和孩子需要的从小到大排序，然后选择按顺序选择饼干。
代码
#include<iostream>
#include<string>
#include<algorithm>
#define maxn 100005
using namespace std;
int main()
{
int N,M,cookie[maxn],stu[maxn];
while(cin>>N>>M&&M)
{
int ans=0;
for(int i=0;i<N;i++)
cin>>cookie[i];
for(int i=0;i<M;i++)
cin>>stu[i];
sort(cookie,cookie+N);
sort(stu,stu+M);
for(int c=0,s=0;s<M&&c<N;c++)
{
if(stu[s]>=cookie[c])
{
ans++;
s++;
}
if(stu[s]<cookie[c])
continue;
}
cout<<ans<<endl;
}
return 0;
}
