算法笔记(4)| 贪心

1.简单贪心

贪心法是求解一类最优化问题的方法，它总是考虑在当前状态下的局部最优（或较优）策略，来使得全局的结果达到最优。举例来说：

【PAT B1020】 月饼

解决这道问题的主要策略是：总是选择单价最高的月饼出售，如果某一种月饼的库存大于市场需求量，则就按照市场需求量将该月饼卖出，否则，就按照月饼的库存将月饼卖完，再按照同样到的方法接着出售下一种类的月饼。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct Moon{
    double store;
    double sell;
    double price;
}moon[1000];

bool cmp(Moon a,Moon b){
    return a.price>b.price;
}

int main(){
    int n;
    double m;
    scanf("%d %lf",&n,&m);  
    for(int i=0;i<n;i++){
        cin>>moon[i].store;
    } 
    for(int i=0;i<n;i++){
        cin>>moon[i].sell;
        moon[i].price=moon[i].sell/moon[i].store;
    }
    double ans=0;
    sort(moon,moon+n,cmp);
    for(int i=0;i<n;i++){
        if(moon[i].store<=m){
            ans=ans+moon[i].sell;
            m=m-moon[i].store;
        }
        else{
            ans=ans+moon[i].price*m;
            break;
        }
    }
    printf("%.2f",ans);
    return 0;
}

【PAT B1023】组个最小数

解决这道题的策略是：首先找到第一位数，即一个非0的数输出放到第一位，并将该数字的次数减一，接着就是按照数字的顺序输出即可。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int count[10];
    for(int i=0;i<10;i++){
        cin>>count[i];
    }
    for(int i=1;i<10;i++){
        if(count[i]>0){
            cout<<i;
            count[i]--;
            break;
        }
    }
    for(int i=0;i<10;i++){
        for(int j=0;j<count[i];j++){
            cout<<i;
        }
    }
    return 0;
}

2.区间贪心

现给出N个开区间(x,y)，从中选择尽可能多的开区间，使得这些开区间两两没有交集。例如给出开区间(1,3)、(2,4)、(3,5)、(6,7)来说，可以选出最多三个区间(1,3)、(3,5)和(6,7)。

解决这道题目的策略是：先将所有的区间按照左端点由大到小进行排列，然后总是选择左端点最大的区间即可。

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
struct Interal{
    int x;
    int y;
}I[1000];

bool cmp(I a,I b){
    if(a.x != b.x){
        return a.x>b.x;
    }
    else{
        return a.y<b.y;
    }
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>I[i].x>>I[i].y;
    }
    sort(I,I+n,cmp);
    int ans=1;
    int lastX=I[0].x;
    for(int i=1;i<n;i++){
        if(I[i].x <= lastX){  //当左端点<=上一个区间的左端点时 
            lastX=I[i].x;
            ans++;
        }
    }
    cout<<ans;
    return 0;
}