贪心算法

求最优方案的时候，每一个步骤都选择当前最优解，这样可以解决整体最优解，那么就可以使用贪心算法

最优子结构问题：全局最优解包含局部最优解

排队接水 1319

struct node{

int val;

int i;

};

bool cmp(node a,node b){

return a.val<b.val;

}

node k[1050];

int main(){

cin>...;

sort(k,k+n);

double sum=0;

for(int i=0;i<n;i++){

cout<<k[i].i<<" ";

sum+=(n-i)*k[i].val;

}

cout<<sum;

}

电池的寿命 1229

输入过程获取最大电池的电量maxa，以及所有电池的电量suma

if(maxa>=suma-maxa){

cout<<suma-maxa;

}

else{

cout<<suma/2;

}

接水问题 1233

for(int i=0;i<n;i++){

cin>>t;

sort(m,m+k);

m[0]+=t;

}

sort(m,m+k);

cout<<m[k-1];

金银岛 1225

int w,s;

double n[10050],v[10050];

while(w--){

cin>>s;

for(int i=1;i<=s;i++){

cin>>n[i]>>v[i];

}

}

struct node{

double n;

double v;

double p;

}k[10050];

bool cmp(node a,node b){

return a.p>b.p;

}

int w,s,t;

double n[10050],v[10050];

cin>>t;

while(t--){

cin>>w>>s;

for(int i=1;i<=s;i++){

cin>>n[i]>>v[i];

k[i].n=n[i];

k[i].v=v[i];

k[i].p=v[i]/n[i];

}

sort(k+1,k+1+s,cmp);

sy=w;

for(int i=1;i<=s;i++){

if(k[i].n>sy){

sum+=k[i].p*sy;

sy=0;

}

else {

sy-=k[i].n;

sum+=k[i].v;

}

if(sy==0) break;

}

cout<<

}

贪心算法进阶作业：

https://www.luogu.com.cn/problem/P1809

ybt.ssoier.cn:8088/problem_show.php?pid=1322