C++新U4-贪心算法1

学习目标

贪心算法的概念

[【贪心算法(一)】书架]

【题意分析】
选出最少的奶牛数量，让他们的身高相加超过书架的高度。

【思路分析】
优先选择身高高的奶牛，这样子奶牛使用的数量最少。

定义排序规则，将数从大到小排序

定义奶牛数量n和书架高度b，并且输入

输入n个奶牛的身高

从大到小排序n个奶牛的身高

定义两个变量，分别为当前已选的奶牛高度和数量

当前加上选择的奶牛高度大于书架的高度

当前加上选择的奶牛高度使得总高度增加，数量+1

输出选择的奶牛数量

【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
int a[20010];
//定义排序规则，将数从大到小排序
bool cmp(int x, int y){
    return x>y;
}
int main() {
    //定义奶牛数量n和书架高度b，并且输入
    int n, b;
    cin >> n >> b;
    //输入n个奶牛的身高
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    //从大到小排序n个奶牛的身高
    sort(a + 1,a + n + 1,cmp);
    //定义两个变量，分别为当前已选的奶牛高度和数量
    int sum = 0, cnt = 0;
    for(int i = 1; i <= n; i++){
        //当前加上选择的奶牛高度使得总高度增加，数量+1
        sum += a[i];
        cnt++;
        //当前加上选择的奶牛高度大于书架的高度，那么退出
        if(sum >= b){
            break;
        }
    }
    //输出选择的奶牛数量
    cout << cnt;
    return 0;
}

[【贪心算法(一)】三角形的最大周长]

【题意分析】
当前要找出三个长度组成的、面积不为零的三角形的最大周长

【思路分析】
我们假设三角形的边长 a,b,c 满足 a≤b≤c，那么这三条边组成面积不为零的三角形的充分必要条件为 a+b>c。

基于此，我们可以选择枚举三角形的最长边 c，而从贪心的角度考虑，我们一定是选「小于 c 的最大的两个数」作为边长 a 和 b，此时最有可能满足 a+b>c，使得三条边能够组成一个三角形，且此时的三角形的周长是最大的。

因此，我们先对整个数组排序，倒序枚举第 i 个数作为最长边，那么我们只要看其前两个数 A[i−2] 和 A[i−1]，判断 A[i−2]+A[i−1] 是否大于 A[i] 即可，如果能组成三角形我们就找到了最大周长的三角形，返回答案 A[i−2]+A[i−1]+A[i] 即可。如果对于任何数作为最长边都不存在面积不为零的三角形，则返回答案 0

定义排序规则进行降序排序

将当前的数组从大到小进行排序

定义一个标记，标记我们并未找到

for循环的方式从前往后找到满足条件的三角形边长

当我们短的两个边相加大于第三边，输出周长，标记已找到

直到最后依旧没有找到符合条件的边

【参考代码】
#include<iostream>
#include<algorithm>
using namespace std;
int arr[110];
//定义排序规则进行降序排序 
bool cmp(int x,int y){
    return x>y;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    //将当前的数组从大到小进行排序 
    sort(arr+1,arr+1+n,cmp);
    //定义一个标记标记我们并未找到 
    bool flag=false;
    //for循环的方式从前往后找到满足条件的三角形边长
    for(int i=1;i<=n-2;i++){
        //当我们短的两个边相加大于第三边，输出周长，标记已找到 
        if(arr[i+1]+arr[i+2]>arr[i]){
            flag=true;
            cout<<arr[i]+arr[i+1]+arr[i+2]<<endl; 
            break;
        }
    }
    //直到最后依旧没有找到符合条件的边 
    if(flag==false)cout<<0<<endl;
    return 0;
}

[【贪心算法(一)】打折糖果]

【题意分析】
找到买完商店所有糖果需要付出的最小的代价

【思路分析】
首先先将糖果价格从大到小排序，当前糖果大于等于3时，按照三个一组的方式，买两个糖果第三个糖果不用钱，取出三个数，如果不足就将剩下的糖果全部买下

定义排序规则进行降序排序

将当前的数组从大到小进行排序

定义变量表示买完糖果的花费

从价格高的糖果开始购买

最后输出小码君的花费

【参考代码】
#include<iostream>
#include<algorithm>
using namespace std;
int arr[110];
//定义排序规则进行降序排序 
bool cmp(int x,int y){
    return x>y;
}
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
    }
    //将当前的数组从大到小进行排序 
    sort(arr+1,arr+1+n,cmp);
    //定义变量表示买完糖果的花费 
    int sum=0;
    //从价格高的糖果开始购买
    for(int i=1;i<=n;i+=3){
        sum+=arr[i];
        if(i+1<=n)sum+=arr[i+1];
    }
    //最后输出小码君的花费
    cout<<sum<<endl; 
    return 0;
}

[【贪心算法(一)】接水问题]

【题意分析】
将n个人排序，谁先去接水，然后去求出一个等待时间最小的。

【思路分析】
平均等待时间 = 总等待时间 / n。当第 i 个接水的人在接水的时候，等待的人数为 n-i，为了总等待时间最少，应该让接水时间短的人先接水，这样其他人等待的时间就会最少。

定义数组储存当前的人的接水耗时

输入n和n个接水的人的用时

将n个人的接水用时从小到大排序

定义一个double变量用于储存所有人的接水等待时间

用for循环将当前人接水等待的时间加到总和中

输出平均值

【参考代码】
#include <iostream>
#include <algorithm>
using namespace std;
//定义数组储存当前的人的接水耗时
int a[1020];
int main() {
    //输入n和n个接水的人的用时
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
    }
    //将n个人的接水用时从小到大排序
    sort(a+1,a+n+1);
    //定义一个double变量用于储存所有人的接水等待时间
    double sum = 0; 
    //用for循环将当前人接水等待的时间加到总和中
    for(int i = 1; i <= n; i++){
        sum += a[i] * (n - i);
    }
    //输出平均值
    printf("%.2f", sum / n);
    return 0;
}

初赛知识：

作业学习系统中有讲解；