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;
}