例题

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<iostream>
#include<algorithm>
#include<cstring>
#include<string>
using namespace std;
const int N=100010;
int p[N];
int n;
int main()
{cin>>n;for(int i=0;i<n;i++) cin>>p[i];int res=0;for(int i=0;i<n-1;i++){int dt=p[i+1]-p[i];if(dt>0) res+=dt;}cout<<res<<endl;return 0;
}

2.货仓选址

题目描述
在一条数轴上有 N 家商店，它们的坐标分别为 A1∼AN。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式
第一行输入整数 N。

第二行 N 个整数 A1∼AN。

输出格式
输出一个整数，表示距离之和的最小值。

数据范围
1≤N≤100000,
0≤Ai≤40000
输入样例：

4
6 2 9 1

输出样例：

12

解题思路

数学证明：

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

#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010;
int a[N];
int main()
{int n;cin>>n;for(int i=0;i<n;i++) cin>>a[i];sort(a,a+n);//对所有商店按位置排序int res=0;for(int i=0;i<n;i++) res+=abs(a[i]-a[n/2]);//n/2就是取所有商店中间的那个货仓，如果n是偶数，就取中间两个左边的一个，如果n是奇数，就是中间那个cout<<res<<endl;
}

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<iostream>
#include<algorithm>
#include<cstring>
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];//求Cc[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<<res<<endl;return 0;
}

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<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int N=1010;
int n,d;
struct Segment{double l,r;bool operator< (const struct Segment& t)const{return r<t.r;}
}seg[N];
int main()
{cin>>n>>d;bool failed=false;for(int i=0;i<n;i++){int x,y;cin>>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<<endl;else{//求一共需要多少雷达sort(seg,seg+n);int cnt=0;double last=-1e20;for(int i=0;i<n;i++){if(seg[i].l>last)//如果该区间没有被上一个雷达检测到，增加一个雷达{cnt++;last=seg[i].r;//该雷达的位置是该区间右端点}}cout<<cnt<<endl;}return 0;
}

蓝桥杯真题

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.当ai<s/n,取bi=ai最小，假设取bi’小于ai，那么一定有一个bj>s/n（因为bi<s/n,要让总和等于s，一定有一个人的贡献大于n/s，才能使总和等于s）
接下来就证明有两个平方和的等式什么时候取最大

证明如下：

所以当两个数的差最小的时候，两个数的平方和最小，那么bi’和bj的差就应该取最小，也就是bi’应该大一点bj小一点，所以bi’应该取ai，这样bj也会小一点（比如我只有2元，另一个人有5元，我们本来应该出6元，即每个人出3元，但我只出1（bi’）元的话，另一个人就要出4（bj）元，那么我们的差值就会很大，但我出2（bi’）元，另一个人出3（bj）元，我们的差值就会变小）

做法：将所有人带的钱数排序，从a1开始，如果a1<n/s，那么第一个人只需要出a1元，剩下的人就出s-a1,第二个人应该出(s-a1)/(n-1)，如果a2<(s-a1)/(n-1),第二个人只需要出a2元，如果大于等于，出(s-a1)/(n-1)即可，以此类推，为什么要排序？因为前面的人钱不够的话，后面钱多的可以补，但如果前面的人是钱多的，他们都只出s/n，后面钱少的就没法补了

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

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
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<n;i++) cin>>a[i];sort(a,a+n);double ave=s/n,res=0;//分别是所有人钱数的均值  所有数的平方和for(int i=0;i<n;i++){double cur=s/(n-i);//第i个人应该出的钱if(a[i]<cur) cur=a[i];//如果不够，就出a[i]res+=(cur-ave)*(cur-ave);//累加平方和s-=cur;//剩下需要出的总钱数 每次减去已经出的钱数}printf("%.4lf",sqrt(res/n));//标准差return 0;
}

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<iostream>
#include<algorithm>
#include<cstring>
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<n;i++) cin>>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<<res<<endl;return 0;
}

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<iostream>
#include<algorithm>
#include<cmath>
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<k;i++) cin>>a[i];if(m==0)//如果没有负数，值就是全部数相加{for(int i=0;i<k;i++) res+=a[i];}else{sort(a,a+k);res+=a[k-1]-a[0];//用最大值减去最小值，最小值是负数for(int i=1;i<k-1;i++) res+=abs(a[i]);//然后其他的减法转化成加法，减去所有负数就是加上所有负数绝对值}cout<<res<<endl;return 0;
}

总结

贪心证明真的很难有没有，考试的时候，如果能想到多半也没时间证明了，所有，靠猜？hhh，多做题总结经验吧 大家加油哦！！

学习网站：AcWing