C++贪心算法

贪心算法

贪心的基本原理:每一步都选择局部最优解而尽量不考虑对后续的影响，最终达到全局最优解。
贪心的局限性:贪心算法不能保证获得全局最》解，但在某些问题上具有高效性。
贪心的特征:贪心选择性质()、最优子结构性质(根据我的观察，很多贪心的题目会出现“不同的操作产生的贡献相同”的特征，在此特征下我们每次选择代价最小的)。

贪心算法实现步骤：

1.确定问题的最优子结构贪心往往和排序、优先队列等一起出现)
“最小代价”。
2.构建贪心选择的策略，可能通过“分类讨论"“最大价值”等方式来思考贪心策略。简单验证贪心的正确性，采用句!般是:这样做一定不会使得结果变差、不存在比当前方案更好的方案等等。
3.通过贪心选择逐步求解问题，直到得到最终解。

例题

蓝桥杯 3412
分析：
简单排序模型。
要将战斗力分为两部分，为了使得差距最小，我们可以将战斗力排序后，找一个位置进行划分，使得左边的都在a，右边的都在b，从而这个差距就是这个位置两边的战斗力差距，说明差距的取值仅有n-1种，枚举即可。
这个题启发我们，当混乱的数据不好处理且排序不影响答案时，尝试先排序再分析

代码如下：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);int ans=a[2]-a[1];for(int i=1;i<n;i++){ans=min(ans,a[i+1]-a[i]);}cout<<ans;return 0;
}

蓝桥杯 545
分析：
总操作数一定情况下的最小代价模型。
我们知道这里一共需要进行的操作次数一定是n-1次，那么贪心地想，如果
每次选择代价最小的两个部落合并，不仅可以使得当前代价最小，还可以使得后续合并的代价也尽可能小。部落大小通过优先队列来维护。

代码如下：

#include <bits/stdc++.h>
using namespace std;int main() {int n;cin >> n;// 使用 lambda 函数作为比较器auto com = [](int a, int b) {return a > b; // 小顶堆};// 定义优先队列，使用自定义的比较器priority_queue<int, vector<int>, decltype(com)> pq(com);// 输入数据并将其推入优先队列for (int i = 1; i <= n; i++) {int x;cin >> x; // 读取输入pq.push(x);}int sum = 0; // 初始化 sum// 合并过程while (pq.size() > 1) { // 确保有至少两个元素int y = pq.top();pq.pop();int z = pq.top(); // 获取下一个元素pq.pop();int ans = y + z; // 合并pq.push(ans); // 将合并后的值推入优先队列sum += ans; // 累加到 sum}cout << sum << endl; // 输出结果return 0;
}

蓝桥杯 532
分析：
最少数目的贪心模型。
为了使得组数最小，我们应该使得每一组内尽可能装两件礼物(最多只能装两件)，尽量占满一组的容量。所以贪心策略是，每一个贵的礼物，带一个便宜的，因为带也是一组，不带也是一组，肯定选择带，且最贵的和最便宜的最容易占满一组

#include<bits/stdc++.h>
using namespace std;const int N=1e5+9;
int a[N];
int main()
{int w;cin>>w;int n;cin>>n;for(int i=1;i<=n;i++){cin>>a[i];}int ans=0;sort(a+1,a+n+1);int l=1;int r=n;while(l<=r){ans++;if(l==r){break;}if(a[l]+a[r]<=w){l++,r--;}else{r--;    }}cout<<ans<<endl;
}

蓝桥杯 2928
找规律的贪心，考验思维，将字符串分类讨论设计贪心策略。
先给字符串排序，然后我们可以分为三类讨论:
1.字符串全相等(假设全a)，那就是尽量使得每个人分到的字符串的最大长度尽可能小就行。
2.s[x]==s[1]，说明第x个是最小的字符带着后面所有的字符一起输出。
3.s[x]!=s[1]，后面一坨字符可以直接丢到s[1]后面，分给第一个同学。

代码如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
char s[N];
int main()
{int n,x;cin>>n>>x;cin>>s+1;sort(s+1,s+n+1);if(s[1]==s[n]){for(int i=1;i<=n/x+(n%x?1:0);i++){cout<<s[1];}}else if(s[x]==s[1]){for(int i=x;i<=n;i++){cout<<s[i];}}else{cout<<s[x];}return 0;
}