时隔多天(bushi)蒟蒻我又来发补题报告了

本次的内容较少主要分为一下几个部分

目录

1.贪心算法的本质

2.贪心算法的步骤(蒟蒻我理解的贪心算法实现的步骤)

3.贪心算法的例题以及例题的解法

---

1.贪心算法的本质

         从问题的初始解出发，一步一步的做出当前最好的选择，尽可能的得到最优解或近似最优解（只根据当前的信息判断，希望通过局部最优得到整体最优）

可用贪心算法求解的重要性质：
        （1）贪心选择：原问题的整体最优解可以有一系列的局部最优解得到，将原问题变成一个相似的规模更小的问题，只依赖于已经做出的选择。
        （2）最优子结构：一个问题的最优解包含其子问题的最优解
解决步骤：（冒泡排序就是一个应用贪心的排序算法）
        （1）确定怎么做才是最好的选择（比如选最大的）
        （2）每一步都做出最优解
        （3）找到一种方式将每一个最优选择组合起来得到答案

2.贪心算法的步骤

（1）确定问题的最优子结构：问题的最优子结构指的是原问题的最优解可以通过其子问题的最优解得到。这一步通常需要根据问题的特性进行分析。

（2）制定贪心策略：贪心策略是贪心算法的核心，它指的是每一步的最优选择方式。贪心策略通常需要满足贪心选择性质，即每一步的最优选择不依赖于之前所做的选择。

（3）实现贪心策略：贪心策略的实现通常涉及到对问题的数据结构和算法的选择，例如贪心策略是基于数值大小的，那么需要使用合适的数据结构（例如优先队列）来存储和获取当前状态下的最优选择。

（4）分析算法的正确性：贪心算法的正确性通常需要通过数学证明来证明它的贪心选择性质以及最终得到的解一定是全局最优解。

（5）分析算法的复杂度：贪心算法的复杂度通常取决于贪心策略的实现以及问题的特性。

需要注意的是：贪心算法只能用在局部最优解能导致全局最优解的问题上

这些呢是蒟蒻我对贪心算法的理解

3.贪心算法的例题以及例题的解法

        这里呢蒟蒻我一共找到了三道有关于贪心的题目

        P3817 - 小A的糖果

        

题目描述

小 A 有 n 个糖果盒，第 i 个盒中有 ai​ 颗糖果。

小 A 每次可以从其中一盒糖果中吃掉一颗，他想知道，要让任意两个相邻的盒子中糖的个数之和都不大于 x，至少得吃掉几颗糖。

输入格式

输入的第一行是两个用空格隔开的整数，代表糖果盒的个数 n 和给定的参数 x。

第二行有 n 个用空格隔开的整数，第 i 个整数代表第 i 盒糖的糖果个数 ai​。

输出格式

输出一行一个整数，代表最少要吃掉的糖果的数量。

输入输出样例

输入 #1

3 3
2 2 2

输出 #1

1

输入 #2

6 1
1 6 1 2 0 4

输出 #2

11

输入 #3

5 9
3 1 4 1 5

输出 #3

0

说明/提示

样例输入输出 1 解释

吃掉第 2 盒中的一个糖果即可。

---

样例输入输出 2 解释

第 2 盒糖吃掉 6 颗，第 4 盒吃掉 2 颗，第 6 盒吃掉 3 颗。

---

数据规模与约定

• 对于 30% 的数据，保证 n≤20，ai​,x≤100。
• 对于 70% 的数据，保证 n≤103，ai​,x≤105。
• 对于 100% 的数据，保证 2≤n≤105，0≤ai​,x≤109。

题目思路：

首先要知道：
第 1 个盒子 只能和 第 2 个盒子分组，而 2 ~ n-1 个糖果 可以和 前 1 个与后 1 个盒子分组；Eg: 第 2 个盒子 与 1、3盒子分组

所以如果只吃掉 第 1 个盒子中的糖果，只减少 1 个分组(1、2盒子)的糖果数量
而如果吃掉 第 2 个盒子中的糖果，则会减少 2 个分组(1、2盒子与2、3盒子)的量
所以整体思路就是，先吃 第一个盒子中的糖果，然后 依次吃掉 每一组(第 i - 1 个盒子 与 第 i 个盒子)中的第 i 个盒子中的糖果

题目代码：

#include <iostream>
#include <algorithm>
using namespace std;
int main( void ){
    long long n, x; // 表示糖果的数量, 表示给定的参数，相邻两数只和 < 给定的参数x
    cin >> n >> x;
    long long sum = 0; // 表示吃掉的糖果的数量
    long long data[ n ]; // 存储每个盒子的糖果数量
    // 对 每个盒子进行输入，以确定糖果的数量
    for ( int i = 0; i < n; i ++ ){
        cin >> data[ i ];
    }
    // 先将第 1 个盒子中的糖果确定下来到底多少个吃掉，然后再依次往后吃，如果第 1 个盒子中的数量 > x，则将第 1 个盒子中的糖果吃到 x 的数量
    if ( data[ 0 ] > x )
    {
        sum = data[ 0 ] - x; // sum --> 存储的是吃掉的糖果的数量 data[ 0 ] - x --> 将多余的糖果吃掉，目的是让第 1 个盒子中的糖果 <= x
        data[ 0 ] = x;
    }
    
    for ( int i = 1; i < n; i ++ ){
        if( data[ i ] + data[ i - 1 ] > x ){ // 如果 第 i 个盒子的糖果 + 第 i-1 个盒子的糖果 > x
            // 让第 2 个盒子中的糖果 被吃掉
            sum += data[ i ] + data[ i - 1 ] - x; // 吃掉的糖果数量 = 第 i 个盒子中的糖果 + 第 i-1 个盒子的糖果 - x
            data[ i ] -= data[ i ] + data[ i - 1 ] - x; // 第 i 个盒子中的糖果 = 第 i 个盒子中的糖果 + 第 i-1 个盒子的糖果 - x
            // 解释 data[ i ] -= data[ i ] + data[ i - 1 ] - x;
                // data[ i ] + data[ i - 1 ] - x --> 表示 【要吃掉的糖果】
                // data[ i ] -= data[ i ] + data[ i - 1 ] - x --> 表示 【第 i 个盒子中的糖果】 - 【要吃掉的糖果】
                // 为什么不从 第 i - 1 个盒子中的糖果中吃掉呢？
                // 因为 前一个盒子已经满足了 < x 的条件(每次循环的前一个(i - 1)盒子就是上一层循环中的第 i 个盒子)，所以如果处理，只需要处理 第 i 个盒子中的糖果就可以了
            // 只减去第 i 个盒子中的糖果，可能会让第 i 个盒子中的糖果 < 0, 所以要对此情况进行判断
            if ( data[ i ] < 0 && data[ i - 1 ] - data[ i ] > 0 ){
                data[ i - 1 ] += -data[ i ]; // 第 i-1 个盒子中的糖果 += 第二个盒子中的 负的糖果 数量 
                data[ i ] = 0; // 第 i 个盒子中的糖果 = 0
            }
        }
    }
    cout << sum;
    return 0;
}

求求大家能不能看在蒟蒻写了这么多的情况下给蒟蒻一个免费的赞呀，谢谢大家了

黑暗料理(kdy贪心)

本题蒟蒻我的思路是直接使用优先队列进行完成(因为一开始没听老师的思路)

#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
const int N=1e6+5;
int n;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	priority_queue<double,vector<double>,greater<double> > a;
	for(int i=1;i<=n;i++){
		double v;
		cin>>v;
		a.push(v);
	}
	while(a.size()>1){
		double x=a.top();
        a.pop();
        double y=a.top();
        a.pop();
        double v1=(x+y)/2.0;
        a.push(v1);
	}
	cout<<fixed<<setprecision(5)<<a.top()<<endl;
	return 0;
}   

这道题的数据以及内存卡的不逝很严，所以这套做法也能过

接下来就是老师讲解的做法了

 
#include<bits/stdc++.h>
#define endl "\n"
using namespace std;
const int N=1e6+5;
double a[N];
int n;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	sort(a+1,a+n+1);
	double sum=a[1];
	for(int i=2;i<=n;i++){
		sum=(sum+a[i])/2;
	}
	printf("%.5lf",sum);
    return 0;
}

最后，感谢LN老师