贪心算法

贪心选择性质就是指，该问题的每一步选择都在选择最优的情况下能够导致最终问题的答案也是最优。即  这一步我这么走一定不会被现在差。

贪心一定要保证无后效性 即对后面的选择无影响

常见的贪心例子：

1.硬币问题：最少硬币问题能否使用贪心法，跟硬币的面值有关。在给定的硬币面值中，若任一面值的硬币，大于比它面值小的硬币的面值和，便可以使用贪心法。 

2. 活动安排问题：解题的关键在于选择什么贪心策列才能安排尽量多的活动 由于活动右开始时间和结束时间 故考虑三种贪心策略 1.最早开始时间 2.最早结束时间 3.用时最少

1.最早开始时间：错误，因为如果一个活动迟迟不终止后面的活动也就无法开始

2.最早结束时间：合理，一盒尽快终止的活动可以容纳更多的后续活动 

 3.用时最早：错误

3.区间覆盖问题：贪心策略：尽量找出更长的线段

解题步骤：1.将每个线段按照左端点递增排序 2.设已经覆盖的区间是[L,R] 在剩下的线段中找所有左端点小于等于R，且右端点最大的线段 加到已经覆盖的区间力 并更新[L,R]的值  重复操作

理解：首先要选择一个左端点最左的线段把（尽可能保证让他右更)然后在此基础上优化)

 

 4.最优装载问题：

装浓度低的肯定不会使得结果变差 而高的可能会使得结果变差 

5.最优装载问题2：

6.多机调度问题： 

 

1.翻硬币 - 蓝桥云课 (lanqiao.cn)

#include 
using namespace std;
const int N=107;
char change(char &ch){
    if(ch=='*') return 'o';
    return '*';
}
 
char a[N];
char b[N];
int main(){
  //读不进去可以尝试 cin>>s+1,cin>>s,cin.ignore(),getline(cin,a),cin.getline(a,N);
    cin.getline(a,N);
    cin.getline(b,N);
    // cin>>(a+1);
    // cin>>(b+1);
    int n = strlen(a);
    int step = 0;
    for(int i = 0; i < n; i++){
        if(a[i] != b[i]){
            a[i] = change(a[i]);
            if(i+1 < n) {
                a[i+1] = change(a[i+1]);
            }
            step++;
        }
    }
    cout << step;
    return 0;
}

 15 届蓝桥杯 14 天省赛冲刺营 1 期 - 找零问题 - 蓝桥云课 (lanqiao.cn)

//当排序后每个面值大于前面小的面值的和的时候可以贪心
#include 
using namespace std;
#define cx first
#define cy second
const int N=1e6+7;
typedef pair<int,int> PII;
int cnt=0;
int n,m;
int a[N];//100 50 20 5 1 
void solve(){ 
    cin>>n;
    int x=n/100;//能换x章100 
    n%=100;//换完x章100后剩下的钱 
    a[1]=x;
    x=n/50;
    n%=50;
    a[2]=x;
    x=n/20;
    n%=20;
    a[3]=x;
    x=n/5;
    n%=5;//换完x章5块后还剩n圆 
    a[4]=x;
    a[5]=n;//此时剩下的是n元
    cout<<"100:"<1]<<'\n';
    cout<<"50:"<2]<<'\n';
    cout<<"20:"<3]<<'\n';
    cout<<"5:"<4]<<'\n';
    cout<<"1:"<5]<<'\n';
}
int main(){
  int t=1;
  while(t--)solve(); 
  return 0;
}

15 届蓝桥杯 14 天省赛冲刺营 1 期 - 小B的宿舍 - 蓝桥云课 (lanqiao.cn)

#include 
using namespace std;
#define cx first
#define cy second
const int N=407;
typedef pair<int,int> PII;
int cnt=0;
int n,m;
int a[N]={0};
void solve(){ 
    cin>>m;
    memset(a,0,sizeof a);
    while(m--){
    	int l,r;cin>>l>>r;
      if(l>r)swap(l,r); //一定要注意 可以反向 这句话的意思
    	if(l%2==0)l--; //如果是2的话 那么其实1也被占了
    	if(r%2==1)r++; //如果是3的话 那么其实4也被占了
    	for(int i=l;i<=r;i++)a[i]++;
	}
	cout<<*max_element(a+1,a+N+1)*10<<'\n';
}
int main(){
  int t=1;cin>>t;
  while(t--)solve(); 
  return 0;
}

 1.快乐司机 - 蓝桥云课 (lanqiao.cn)

#include
using namespace std;
//using ll=long long;
//只需要找到  价值/重量  最大的，将他放在前面
//直接加起来就能得到答案，注意使用double
bool cmp(pair<double,double>&a,pair<double,double>&b){
    return a.second/a.first>b.second/b.first;
}
 
int main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);    
    int n,w;cin>>n>>w;
    pair<double,double>pa[n];
    for(int i=0;i
        cin>>pa[i].first>>pa[i].second;
    }
    sort(pa,pa+n,cmp);
    double ans=0;
    for(int i=0;i
        if(pa[i].first<=w){
            ans+=pa[i].second;
            w-=pa[i].first;
        }
        else if(w>0&&pa[i].first>w){//还能装 但是装不完
            double temp=pa[i].second/pa[i].first;
            ans+=w*temp;
            break;
        }
        if(w==0){//再也不能装了
            break;
        }
    }
    printf("%.1lf",ans);
    return 0;
}

 1.答疑 - 蓝桥云课 (lanqiao.cn)

 

#include
using namespace std;
#define int long long
const int N=1e6+7;
int n; 
struct st{
	int s;
	int a;
	int e;
}stu[N];
bool cmp(st x,st y){
	int temp1=x.s+x.a+x.e;
	int temp2=y.s+y.a+y.e;
	return (temp1!=temp2?temp1
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);    
    cin>>n;//问完就发 
    for(int i=1;i<=n;i++)cin>>stu[i].s>>stu[i].a>>stu[i].e;
	sort(stu+1,stu+n+1,cmp);
	int sum=0;//截至到上一个学生用的总时间
	int ans=0;
	for(int i=1;i<=n;i++){//该第ans个学生问了 
		ans+=(sum+stu[i].s+stu[i].a);
		sum+=(stu[i].s+stu[i].a+stu[i].e);
	} 
	cout<
    return 0;
}

 1.防御力 - 蓝桥云课 (lanqiao.cn)

#include 
using namespace std;
const int MAX=1000;
//B从大到小使用 A从小到大使用 多试几组数据可以得到
struct node_A{
    int id=0;
    int dA=0;
}A[MAX];
struct node_B{
    int id=0;
    int dB=0;
}B[MAX];
 
bool cmpa(node_A a,node_A b){
    if(a.dA!=b.dA){
        return a.dA
    }else{
        return a.id
    }
}
bool cmpb(node_B a,node_B b){
    if(a.dB!=b.dB){
        return a.dB>b.dB;
    }else{
        return a.id
    }
}
 
int main(){
   int n1,n2;cin >>n1>>n2;
 
   for(int i=1;i<=n1;i++){
           cin >>A[i].dA;
           A[i].id=i; 
   }
   sort(A+1,A+n1+1,cmpa);
    for(int i=1;i<=n2;i++){
           cin >>B[i].dB;
           B[i].id=i; 
    }
    sort(B+1,B+n2+1,cmpb);
    int dex1=1,dex2=1; 
    string str;cin>>str;
    for(int i=0;isize();i++){
        if(str[i]=='0'){
            cout<<"A"<'\n';
        }else{
            cout<<"B"<'\n';
        }
    } 
    cout<<"E"<<'\n';
    return 0;
}

 

 

 

#inclued 
using namespace std;
//需要一个结构体，通过性价比，能够查找到重量和价值。
//做一个排序，需要将性价比由高到底排序，排序的过程中重量和（价值）要对应上
struct Food{
    double w;
    double v;
    double aver;
 
};
bool cmp(Food a, Food b){
    return a.aver > b.aver;
    //助记大于号就是从大到小排序，小于号就是从小到大排序
}
int main(){
    Food foods[1009];
    int n;
    double C;
    double Value = 0;
    cin >> n >> C;
    for (int i = 0; i < n; i++)
    {
        cin >> foods[i].v>>foods[i].w;
        //求性价比
        foods[i].aver = foods[i].v / foods[i].w;
        //cout << foods[i].aver << '\n';
 
    }
    //性价比排序
    sort(foods, foods + n, cmp);
 
    //当背包（肚子）能装下所有物品（菜）时，直接输出所有的物品（菜品）价值之和
    int sum = 0;
    for (int i = 0; i < n; i++){
        sum += foods[i].w;
    }
    if (sum <= C){
        for (int j = 0; j < n; j++)
            Value += foods[j].v;
        //V = floor(V * 1000.0) / 1000.0;
        cout << setiosflags(ios::fixed) << setprecision(3) <
        return 0;
    }
 
    //当背包（肚子）不能装下所有物品时应该由性价比的顺序，选择装入的物品
 
    for (int i = 0; i < n; i++)
    {
        if (foods[i].w <= C)
        {
            Value =Value + foods[i].v;
            C = C - foods[i].w;
        }
        else
        {
            //直接将剩余的C加入即可
            Value =Value + C * foods[i].aver;
            C = 0;
        }
        if (C == 0)
            break;
    }
    //V = floor(V * 1000.0) / 1000.0;
    printf("%.3lf\n",Value);
    return 0;
}

贪心算法的最主要的特征就是无后效性，就像是自助餐那个题目，如果说吃了某一样食物，就不能吃另一个食物了，那么这就有了后效性，那就不能使用贪心算法进行解决问题了。