2022蓝桥杯学习——7.贪心

2022蓝桥杯学习——7.贪心 例题 1.股票买卖

题目描述
给定一个长度为 N 的数组，数组中的第 i 个数字表示一个给定股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

输入格式
第一行包含整数 N，表示数组长度。

第二行包含 N 个不大于 10000 的正整数，表示完整的数组。

输出格式
输出一个整数，表示最大利润。

数据范围
1≤N≤105
输入样例1：

6
7 1 5 3 6 4

输出样例1：

7

输入样例2：

5
1 2 3 4 5

输出样例2：

4

输入样例3：

5
7 6 4 3 1

输出样例3：

0

样例解释
样例1：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。共得利润 4+3 = 7。

样例2：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

样例3：在这种情况下, 不进行任何交易, 所以最大利润为 0。

解题思路

看到这道题想到了在LeetCode做的这道题买股票的最佳时机，不同的是，股票买卖这个题可以进行多次交易，我们可以在任何时候选择卖出或者买入，只要最后的利润最大就行，本题的贪心是：只要相邻的两个时机，前面的价格小于后面的价格，我们就交易一次。肯定是后面的价格高了卖出才会有利润，但如果只是在价格最低的时候买入，价格最高的时候卖出不一定就是最大利润，比如样例一，因为在这之前或者之后我们也可以进行交易。

代码实现+详细注释C++

#include
#include
#include
#include
using namespace std;
const int N=100010;
int p[N];
int n;
int main()
{
    cin>>n;
    for(int i=0;i>p[i];
    int res=0;
    for(int i=0;i0) res+=dt;
    }
    cout< 
2.货仓选址 
题目描述
 在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。
 
现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。
 
为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。
 
输入格式
 第一行输入整数 N。
 
第二行 N 个整数 A1∼AN。
 
输出格式
 输出一个整数，表示距离之和的最小值。
 
数据范围
 1≤N≤100000,
 0≤Ai≤40000
 输入样例：
 
 
 
4
 6 2 9 1
 
 
输出样例：
 
 
 
12
 
 
解题思路
 
 
 

 数学证明：
 
 
 
代码实现+详细注释C++
 
#include
#include
using namespace std;
const int N=100010;
int a[N];
int main()
{
    int n;
    cin>>n;
    for(int i=0;i>a[i];
    sort(a,a+n);//对所有商店按位置排序
    int res=0;
    for(int i=0;i 
3.糖果传递 
题目描述
 有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。
 
每人只能给左右两人传递糖果。
 
每人每次传递一个糖果代价为 1。
 
求使所有人获得均等糖果的最小代价。
 
输入格式
 第一行输入一个正整数 n，表示小朋友的个数。
 
接下来 n 行，每行一个整数 a[i]，表示第 i 个小朋友初始得到的糖果的颗数。
 
输出格式
 输出一个整数，表示最小代价。
 
数据范围
 1≤n≤1000000,
 0≤a[i]≤2×109,
 数据保证一定有解。
 
输入样例：
 
 
 
4
 1
 2
 5
 4
 
 
输出样例：
 
 
 
4
 
 
解题思路
 
 
 

 
 
 转化完之后，这道题就和上道题一样了
 >
 所以先由A数组，用公式求出C数组，得到C数组之后就跟上一题一样，找一个点，使这个点到C数组所有点的距离之和最小
 
 
代码实现+详细注释C++
 
#include
#include
#include
using namespace std;
const int N=1000010;
typedef long long LL;
int a[N];
LL c[N];
LL sum;
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++) sum+=a[i];
    int ave=sum/n;//求糖果的平均数
    for(int i=n;i>1;i--) c[i]=c[i+1]+ave-a[i];//求C
    c[1]=0;
    sort(c+1,c+n+1);
    LL res=0;
    for(int i=1;i<=n;i++) res+=abs(c[i]-c[(i+1)/2]);//通过C求所有距离之和的最小值
    cout< 
4.雷达设备 
题目描述
 假设海岸是一条无限长的直线，陆地位于海岸的一侧，海洋位于另外一侧。
 
每个小岛都位于海洋一侧的某个点上。
 
雷达装置均位于海岸线上，且雷达的监测范围为 d，当小岛与某雷达的距离不超过 d 时，该小岛可以被雷达覆盖。
 
我们使用笛卡尔坐标系，定义海岸线为 x 轴，海的一侧在 x 轴上方，陆地一侧在 x 轴下方。
 
现在给出每个小岛的具体坐标以及雷达的检测范围，请你求出能够使所有小岛都被雷达覆盖所需的最小雷达数目。
 
输入格式
 第一行输入两个整数 n 和 d，分别代表小岛数目和雷达检测范围。
 
接下来 n 行，每行输入两个整数，分别代表小岛的 x，y 轴坐标。
 
同一行数据之间用空格隔开。
 
输出格式
 输出一个整数，代表所需的最小雷达数目，若没有解决方案则所需数目输出 −1。
 
数据范围
 1≤n≤1000,
 −1000≤x,y≤1000
 输入样例：
 
 
 
3 2
 1 2
 -3 1
 2 1
 
 
输出样例：
 
 
 
2
 
 
解题思路
 
 
 
不考虑每个雷达可以覆盖多少区间，而是考虑对于每个小岛，能覆盖它的雷达区间是多少，那么只要对于每个小岛的区间上有雷达，小岛就可以被覆盖，所以看所有的小岛，对于所有的区间，都要至少有一个雷达
 
 
 
 
 
代码实现+详细注释C++
 
#include
#include
#include
#include
using namespace std;
const int N=1010;
int n,d;
struct Segment{
    double l,r;
    bool operator< (const struct Segment& t)const{
        return r>n>>d;
    bool failed=false;
    for(int i=0;i>x>>y;
        if(y>d) failed=true;//直线距离最短，如果最短距离都大于d，说明雷达检测不到
        else{
            double len=sqrt(d*d-y*y);
            seg[i].l=x-len,seg[i].r=x+len;//该岛屿 雷达可检测到的区间
        }
    }
    if(failed) cout<<-1<last)//如果该区间没有被上一个雷达检测到，增加一个雷达
            {
                cnt++;
                last=seg[i].r;//该雷达的位置是该区间右端点
            }
        }
        cout< 
蓝桥杯真题 
1.付账问题 
题目描述
 几个人一起出去吃饭是常有的事。
 
但在结帐的时候，常常会出现一些争执。
 
现在有 n 个人出去吃饭，他们总共消费了 S 元。
 
其中第 i 个人带了 ai 元。
 
幸运的是，所有人带的钱的总数是足够付账的，但现在问题来了：每个人分别要出多少钱呢？
 
为了公平起见，我们希望在总付钱量恰好为 S 的前提下，最后每个人付的钱的标准差最小。
 
这里我们约定，每个人支付的钱数可以是任意非负实数，即可以不是 1 分钱的整数倍。
 
你需要输出最小的标准差是多少。
 
标准差的介绍：标准差是多个数与它们平均数差值的平方平均数，一般用于刻画这些数之间的“偏差有多大”。
 
形式化地说，设第 i 个人付的钱为 bi 元，那么标准差为 :
 
 输入格式
 第一行包含两个整数 n、S；
 
第二行包含 n 个非负整数 a1, …, an。
 
输出格式
 输出最小的标准差，四舍五入保留 4 位小数。
 
数据范围
 1≤n≤5×10^5,
 0≤ai,S≤10^9
 输入样例1：
 
 
 
5 2333
 666 666 666 666 666
 
 
输出样例1：
 
 
 
0.0000
 
 
输入样例2：
 
 
 
10 30
 2 1 4 7 4 8 3 6 4 7
 
 
输出样例2：
 
 
 
0.7928
 
 
解题思路
 
 
 

 证明贪心的成立
 1.ai>=(s/n)时，取bi=s/n最小，将(bi-s/n)看做xi，证明如下：
 
 2.当ais/n（因为bi 接下来就证明有两个平方和的等式什么时候取最大
 
 证明如下：
 
 所以当两个数的差最小的时候，两个数的平方和最小，那么bi’和bj的差就应该取最小，也就是bi’应该大一点bj小一点，所以bi’应该取ai，这样bj也会小一点（比如我只有2元，另一个人有5元，我们本来应该出6元，即每个人出3元，但我只出1（bi’）元的话，另一个人就要出4（bj）元，那么我们的差值就会很大，但我出2（bi’）元，另一个人出3（bj）元，我们的差值就会变小）
 
 
做法：将所有人带的钱数排序，从a1开始，如果a1 
 
代码实现+详细注释C++
 
#include
#include
#include
#include
#include
using namespace std;
const int N=500010;
int a[N];
typedef long long LL;
int main()
{
    int n;
    double s;
    cin>>n>>s;
    for(int i=0;i>a[i];
    sort(a,a+n);
    double ave=s/n,res=0;//分别是所有人钱数的均值  所有数的平方和
    for(int i=0;i 
2.乘积最大 
题目描述
 给定 N 个整数 A1,A2,…AN。
 
请你从中选出 K 个数，使其乘积最大。
 
请你求出最大的乘积，由于乘积可能超出整型范围，你只需输出乘积除以 1000000009 的余数。
 
注意，如果 X<0， 我们定义 X 除以 1000000009 的余数是负(−X)除以 1000000009 的余数，即：0−((0−x)%1000000009)
 输入格式
 第一行包含两个整数 N 和 K。
 
以下 N 行每行一个整数 Ai。
 
输出格式
 输出一个整数，表示答案。
 
数据范围
 1≤K≤N≤10^5,
 −105≤Ai≤10^5
 输入样例1：
 
 
 
5 3
 -100000
 -10000
 2
 100000
 10000
 
 
输出样例1：
 
 
 
999100009
 
 
输入样例2：
 
 
 
5 3
 -100000
 -100000
 -2
 -100000
 -100000
 
 
输出样例2：
 
 
 
-999999829
 
 
解题思路
 
 
 

 将所有数排序后，左边是负数绝对值最大的数，右边是正数最大的，如果要选奇数个数，我们先选最右边的数，用两个指针分别指向待选的数的最左边和待选的数的最右边，每次从左边选两个数相乘，再从右边选两个数相乘，比较两个乘积，选择大的，再移动指针，直到选完k个数，如果是偶数个，直接一对一对的选就行了。
 
 
代码实现+详细注释C++
 
#include
#include
#include
using namespace std;
const int N=100010,mod=1000000009;
typedef long long LL;
int a[N];
int n,k;
int main()
{
    cin>>n>>k;
    for(int i=0;i>a[i];
    sort(a,a+n);
    int res=1;
    int l=0,r=n-1;
    int sign=1;//标记全是负数的情况
    if(k%2)//如果是奇数个，先取最后一个
    {
        res=a[r--];
        k--;
        if(res<0) sign=-1;//如果最后一个也是负数，那就标记
    }
    while(k)
    {
        LL x=(LL)a[l]*a[l+1],y=(LL)a[r-1]*a[r];//从左边和右边各取两个相乘
        if(x*sign>y*sign)//如果sign=-1，则说明都是负数，去最小的
        {
            res=x%mod*res%mod;
            l+=2;//移动指针
        }
        else
        {
            res=y%mod*res%mod;
            r-=2;
        }
        k-=2;
    }
    cout< 
3.后缀表达式 
题目描述
 给定 N 个加号、M 个减号以及 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1，小明想知道在所有由这 N 个加号、M 个减号以及 N+M+1 个整数凑出的合法的后缀表达式中，结果最大的是哪一个？
 
请你输出这个最大的结果。
 
例如使用 123+−，则 “23+1−” 这个后缀表达式结果是 4，是最大的。
 
输入格式
 第一行包含两个整数 N 和 M。
 
第二行包含 N+M+1 个整数 A1,A2,⋅⋅⋅,AN+M+1。
 
输出格式
 输出一个整数，代表答案。
 
数据范围
 0≤N,M≤10^5,
 −109≤Ai≤10^9
 输入样例：
 
 
 
1 1
 1 2 3
 
 
输出样例：
 
 
 
4
 
 
解题思路
 
 
 
后缀表达式是借助栈来实现的，用一个栈来存数，当遇到运算符号的时候将栈顶两个元素出栈进行运算，结果再放回栈中。
 后缀表达式也可转化成一棵二叉树，这可数的后序遍历就是表达式后缀表达式，如下：
 
 如果想让N+M+1个数加减之后值最大，直观想法就是减去所有的负数加上所有的正数，但是由于减号和加号是固定的，所有应该尽量减去更多的负数，如果负数不够减去小的正数。b1-(a1-a2-a3-a4)=b1-a1+a2+a3+a4 ，那么1~M个负数，就可以凑出只有一个负数,也就是可以凑出任意1~M个负数，如果有N个正数，正数也可凑成负数。就可以凑出任意1~N+M个负数
 
 所以如果有负号，无论怎么弄，都一定有一个减号，如果减法想变大，那这个减号后面一定是一个最小值（负数里绝对值最大），剩下的加法，一定是尽量加上最大值
 
 做法：如果M<0，没有减号，所以就所有数相加就是最大值，如果有减号，用最大值减去最小值加上剩下的数的绝对值就行。因为只要表达式有一个减号就行，剩下的减号都可以转化成加号。
 
 
代码实现+详细注释C++
 
#include
#include
#include
using namespace std;
const int N=200010;
typedef long long LL;
int a[N];
int n,m;
LL res;
int main()
{
    cin>>n>>m;
    int k=n+m+1;
    for(int i=0;i>a[i];
    
    if(m==0)//如果没有负数，值就是全部数相加
    {
        for(int i=0;i 
总结 
 
 
贪心证明真的很难有没有，考试的时候，如果能想到多半也没时间证明了，所有，靠猜？hhh，多做题总结经验吧 大家加油哦！！
 
 
学习网站：AcWing
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5718408.html