贪心算法

程序1:字典序的字符串拼接
程序2:切金条

#include<iostream> //切金条,使用了优先级队列
using namespace std;
#include<string>
#include<limits.h>
#include<vector>
#include<unordered_map>
#include<queue>

int lessMoney(int* arr,int l)
{
    priority_queue<int, vector<int>, greater<int> >pQ;
    for(int i = 0;i<l;i++)
    {

        pQ.push(arr[i]);
    }

    int sum = 0;
    int cur = 0;
    while (pQ.size()>1)   //注意这里的条件
    {
        cur = pQ.top();
        pQ.pop();
        cur += pQ.top();
        sum+=cur;
        pQ.pop();
        pQ.push(cur);
    }
    return sum;
}

int main() 
{
    int arr[] = {10,2,3,16};
    cout<<lessMoney(arr,sizeof(arr) / sizeof(int));
    return 0;
}

程序3:项目的最大收益,优先队列,自定义比较器,new class类型的数组

#include<iostream> //项目最大收益
using namespace std;
#include<string>
#include<limits.h>
#include<vector>
#include<unordered_map>
#include<queue>

class Node
{
public:
    Node(){};   //要加默认构造
    Node(int c,int y)
    {
        this->c = c;
        this->p = p;
    }
    int p;
    int c;
};
class compater1  //成本的比较器
{
public:
    bool operator()(Node &a,Node &b)
    {
        return a.c > b.c;
    }
};

class compater2 //利润的比较器
{
public:
    bool operator()(Node &a,Node &b)
    {
        return a.p < b.p;
    }
};
int findMaximizedCapital(int k,int w, vector<int> cost,vector<int> profits)
{
    priority_queue<Node, vector<Node>, compater1> mincostQ; //成本为小根堆
    priority_queue<Node, vector<Node>, compater2> maxProfitQ; //利润为大根堆
    Node* nodes = new Node[cost.size()];
    for(int i = 0;i<cost.size();i++)
    {
        nodes[i].c = cost[i];
        nodes[i].p = profits[i];
    }
    for(int i = 0;i<cost.size();i++)
    {
        mincostQ.push(nodes[i]);
    }
    for(int i = 0;i<k;i++)
    {
        while(!mincostQ.empty()&&mincostQ.top().c <= w)
        {
            maxProfitQ.push(mincostQ.top());
            mincostQ.pop();
        }
        if(!maxProfitQ.empty())
        {
            w+= maxProfitQ.top().p;
            maxProfitQ.pop();
        }
        else
        {
            return w;
        }
    }
    delete[] nodes;
    return w;
}

int main() 
{
    vector<int> profits;
    vector<int> costs;

    profits.push_back(7);
    profits.push_back(16);
    profits.push_back(30);

    costs.push_back(5);
    costs.push_back(10);    
    costs.push_back(15);
    cout<<findMaximizedCapital(4,8,costs,profits)<<endl;
    return 0;
}

程序4:会议次数最多,vector中实现比较器

#include<iostream> //会议次数最多
using namespace std;
#include<string>
#include<limits.h>
#include<vector>
#include<unordered_map>
#include<queue>
#include<algorithm>

class Progarme
{
public:
    Progarme(int start,int end)
    {
        this->start = start;
        this->end = end;
    }
    int start;
    int end;
};

bool compater(Progarme& a,Progarme& b)
{
    return a.end < b.end;
}
int bestArrange(vector<Progarme> programe,int cur)
{
    sort(programe.begin(),programe.end(),compater);
    int result = 0;
    for(int i = 0;i<programe.size();i++)
    {
        if(programe[i].start >= cur)
        {
            result++;
            cur = programe[i].end;
        }
    }
    return result;
}

int main() 
{
    vector<Progarme> p;
    p.push_back(Progarme(1,3));
    p.push_back(Progarme(2,4));
    p.push_back(Progarme(2,5));
    p.push_back(Progarme(4,6));
    cout<<bestArrange(p, 0);
    return 0;
}