讨论 / c++ 贪心代码,使用了heap的方法和自定义的排序方式
tjsudys 2016-04-12 15:05:28
点我顶贴 收藏 删除
#include <iostream>

#include <algorithm>

#include <vector>

struct lessss{

bool operator()(int a,int b)

{

return a>b;

}

};

using namespace std;

vector<int> vec;

int main() {

int N;

cin>>N;

for(int i=0;i<N;i++)

{

int z;

cin>>z;

vec.push_back(z);

push_heap(vec.begin(),vec.end(),lessss());

}

int cost = 0;

int xcost = 0;

while(vec.size()!=1)

{

xcost += vec.front();

pop_heap(vec.begin(),vec.end(),lessss());

vec.pop_back();

xcost+=vec.front();

pop_heap(vec.begin(),vec.end(),lessss());

vec.pop_back();

vec.push_back(xcost);

push_heap(vec.begin(),vec.end(),lessss());

cost+=xcost;

cout<<xcost;

xcost=0;

}

cout<<cost<<endl;

// your code goes here

return 0;

}

为了回顾下如何使用heap和自定义排序,写的有点复杂。

#1 flyingzld@2016-04-15 12:47:01
回复 删除
wdfasdfasdf
查看更多回复
提交回复