[挑战十四天拿下蓝桥杯]第一天贪心算法

本文主要是介绍[挑战十四天拿下蓝桥杯]第一天贪心算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

贪心

贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。

例题

X进制减法

这题需要注意数据类型的设计( 开 long long )
计算进制时需要取余 ( 否则会溢出 )

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main()
{// 321int N;cin >> N;// 两个数组数组数字int arr1[100004];int arr2[100004];int arr3[100004]; // 相减之后int n1;cin >> n1;for (int i = n1 - 1; i >= 0; i--){cin >> arr1[i];}int n2;cin >> n2;for (int i = n2 - 1; i >= 0; i--){cin >> arr2[i];}// 相减之后for (int i = 0; i < n1; i++){arr3[i] = arr1[i] - arr2[i];}// 遍历两个数组 然后找出符合要求进制long long weight, res = 0; // weight 表示进制long long pos = 1; // 用于累乘for (int i = 0; i < n1; i++){// weight = max(arr1[i], arr2[i], 2); // 取最大值if(arr1[i] <2 && arr2[i]< 2) {weight = 2;} else if(arr1[i] > arr2[i]){weight = arr1[i]+1;} else {weight = arr2[i]+1;}res =(res +  pos * arr3[i])%1000000007;pos = (pos *  weight)%1000000007;}cout<<res<<endl;return 0;
}

这篇关于[挑战十四天拿下蓝桥杯]第一天贪心算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---