C++贪默算法

贪默算法

贪心的根本原理:每一步都选择局部最优解而只管不思量对后续的影响，终极到达全局最优解。
贪心的范围性:贪默算法不能包管得到全局最》解，但在某些标题上具有高效性。
贪心的特性:贪心选择性子()、最优子结构性子(根据我的观察，许多贪心的标题会出现“差异的利用产生的贡献类似”的特性，在此特性下我们每次选择代价最小的)。
贪默算法实现步调：

1.确定标题的最优子结构贪心通常和排序、优先队列等一起出现)
“最小代价”。
2.构建贪心选择的计谋，大概通过“分类讨论"“最大代价”等方式来思考贪心计谋。简朴验证贪心的准确性，接纳句!般是:如许做肯定不会使得效果变差、不存在比当火线案更好的方案等等。
3.通过贪心选择渐渐求解标题，直到得到终极解。
例题

蓝桥杯 3412
分析：
简朴排序模子。
要将战斗力分为两部分，为了使得差距最小，我们可以将战斗力排序后，找一个位置举行分别，使得左边的都在a，右边的都在b，从而这个差距就是这个位置两边的战斗力差距，分析差距的取值仅有n-1种，罗列即可。
这个题开导我们，当杂乱的数据欠长处理且排序不影响答案时，实行先排序再分析
代码如下：

1. #include <bits/stdc++.h>
2. using namespace std;
3. const int N = 1e5 + 10;
4. int a[N];
5. int main()
6. {
7.   int n;cin>>n;
8.   for(int i=1;i<=n;i++)
9.   {
10.     cin>>a[i];
11.   }
12.   sort(a+1,a+n+1);
13.   int ans=a[2]-a[1];
14.   for(int i=1;i<n;i++)
15.   {
16.     ans=min(ans,a[i+1]-a[i]);
17.   }
18.   cout<<ans;
19.   return 0;
20. }

复制代码

蓝桥杯 545
分析：
总利用数肯定环境下的最小代价模子。
我们知道这里一共须要举行的利用次数肯定是n-1次，那么贪心地想，假如
每次选择代价最小的两个部落归并，不光可以使适当前代价最小，还可以使得后续归并的代价也尽大概小。部落巨细通过优先队列来维护。
代码如下：

1. #include <bits/stdc++.h>
2. using namespace std;
4. int main() {
5.     int n;
6.     cin >> n;
8.     // 使用 lambda 函数作为比较器
9.     auto com = [](int a, int b) {
10.         return a > b; // 小顶堆
11.     };
12.    
13.     // 定义优先队列，使用自定义的比较器
14.     priority_queue<int, vector<int>, decltype(com)> pq(com);
15.    
16.     // 输入数据并将其推入优先队列
17.     for (int i = 1; i <= n; i++) {
18.         int x;
19.         cin >> x; // 读取输入
20.         pq.push(x);
21.     }
23.     int sum = 0; // 初始化 sum
24.     // 合并过程
25.     while (pq.size() > 1) { // 确保有至少两个元素
26.         int y = pq.top();
27.         pq.pop();
28.         int z = pq.top(); // 获取下一个元素
29.         pq.pop();
30.         int ans = y + z; // 合并
31.         pq.push(ans); // 将合并后的值推入优先队列
32.         sum += ans; // 累加到 sum
33.     }
35.     cout << sum << endl; // 输出结果
36.     return 0;
37. }

复制代码

蓝桥杯 532
分析：
最少数量的贪心模子。
为了使得组数最小，我们应该使得每一组内尽大概装两件礼物(最多只能装两件)，只管占满一组的容量。以是贪心计谋是，每一个贵的礼物，带一个自制的，由于带也是一组，不带也是一组，肯定选择带，且最贵的和最自制的最容易占满一组

1. #include<bits/stdc++.h>
2. using namespace std;
4. const int N=1e5+9;
5. int a[N];
6. int main()
7. {
8.   int w;cin>>w;
9.   int n;cin>>n;
10.   for(int i=1;i<=n;i++)
11.   {
12.     cin>>a[i];
13.   }
14.   int ans=0;
15.   sort(a+1,a+n+1);
16.   int l=1;int r=n;
17.   while(l<=r)
18.   {
19.     ans++;
20.     if(l==r)
21.     {
22.       break;
23.     }
24.     if(a[l]+a[r]<=w)
25.     {
26.       l++,r--;
27.     }
28.     else
29.     {
30.       r--;   
31.     }
32.   }
33.   cout<<ans<<endl;
34. }

复制代码

蓝桥杯 2928
找规律的贪心，磨练头脑，将字符串分类讨论计划贪心计谋。
先给字符串排序，然后我们可以分为三类讨论:
1.字符串全相当(假设全a)，那就是只管使得每个人分到的字符串的最大长度尽大概小就行。
2.s[x]==s[1]，分析第x个是最小的字符带着反面全部的字符一起输出。
3.s[x]!=s[1]，反面一坨字符可以直接丢到s[1]反面，分给第一个同砚。
代码如下：

1. #include<bits/stdc++.h>
2. using namespace std;
3. const int N=1e6+10;
4. char s[N];
5. int main()
6. {
7.   int n,x;
8.   cin>>n>>x;
9.   cin>>s+1;
10.   sort(s+1,s+n+1);
11.   if(s[1]==s[n])
12.   {
13.     for(int i=1;i<=n/x+(n%x?1:0);i++)
14.     {
15.       cout<<s[1];
16.     }
17.   }
18.   else if(s[x]==s[1])
19.   {
20.     for(int i=x;i<=n;i++)
21.     {
22.       cout<<s[i];
23.     }
24.   }
25.   else{
26.     cout<<s[x];
27.   }
28.   return 0;
29. }

复制代码