【算法】反悔贪心

69 阅读 0 评论 46 点赞

我是靠谱客的博主热情朋友，最近开发中收集的这篇文章主要介绍【算法】反悔贪心，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

通常来讲，贪心向来是取局部最优解，但是局部最优解最后不一定构成整体最优解，因而就有了反悔这个操作，来优化贪心。
而构成反悔贪心，通常会有一个限制条件。
例如，我们假设数组array{1，5，6，7，2，6，7，9，4，3，5，1}；如果我们要求取k个数，使其取得最大值，显然此时我们的贪心策略是对array数组进行排序，取前k大的数据加起来就得到结果。但是当我加一个限制条件，不允许取相邻的两个数，也就是说当你取了位置i上的数时，位置i-1和位置i+1的值就不能取了，此时若按照上述贪心策略取贪心，则不能确保整体最优解。
举个最简单的例子，对于{4，5，2}，如果我们取了5，则不能取4和2，但我们发现我们可以不取5，转而取4和2，而此时获得的值为4+2=6，是大于5的。这时我们发现我们第一个贪心策略是不完美了，我们需要进行反悔操作，才能达到最优解。
那么如何进行反悔操作呢。我们假设数值5对应的位置为i；则4的位置为i-1，2的位置为i+1，namo我们可以设一个大根堆存储各个元素的值及其对应的位置，首先我们采取最开始的贪心策略，我们把5给拿走，此时我们可以处理一个反悔操作，令a[i] = a[i+1] +a[i-1] -a[i] ；并将这个更新的值加入大根堆中，若我们可以取到这个值，显然更新后的a[i]含有的a[i] 项就会和我们之前贪心选择的a[i] 项消掉，留下a[i+1] 和a[i-1]，这便完成了一次反悔贪心，以此类推，从小及大，最终即可得到最优解。
在这里我推荐两道例题去具体熟练一下操作：
一、洛谷的种树.
AC代码：

/*
 * @Author: csc
 * @Date: 2021-04-05 15:29:23
 * @LastEditTime: 2021-04-06 19:32:17
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: code_formalcfCF_712_4_.cpp
 */
#include <bits/stdc++.h>
#define pr printf
#define sc scanf
#define sf(n) scanf("%d", &n)
#define sff(n1, n2) scanf("%d %d", &n1, &n2)
#define sfff(n1, n2, n3) scanf("%d %d %d", &n1, &n2, &n3)
#define sl(n) scanf("%lld", &n)
#define sll(n1, n2) scanf("%lld %lld", &n1, &n2)
#define slll(n1, n2, n3) scanf("%lld %lld %lld", &n1, &n2, &n3)
#define for0(i, n) for (i = 0; i < n; i++)
#define for1n(i, n) for (i = 1; i <= n; i++)
#define foran(i, a, n) for (i = a; i <= n; i++)
#define forna(i, a, n) for (i = n; i >= a; i--)
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl 'n'
#define mem(ara, n) memset(ara, n, sizeof(ara))
#define memb(ara) memset(ara, false, sizeof(ara))
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define sz(x) x.size()
const int N = 2e5 + 100;
const int mod = 1e9 + 7;
namespace fastIO
{
    inline void input(int &res)
    {
        char c = getchar();
        res = 0;
        int f = 1;
        while (!isdigit(c))
        {
            f ^= c == '-';
            c = getchar();
        }
        while (isdigit(c))
        {
            res = (res << 3) + (res << 1) + (c ^ 48);
            c = getchar();
        }
        res = f ? res : -res;
    }
    inline int qpow(int a, int b)
    {
        int ans = 1, base = a;
        while (b)
        {
            if (b & 1)
                ans = (ans * base % mod + mod) % mod;
            base = (base * base % mod + mod) % mod;
            b >>= 1;
        }
        return ans;
    }
    int fact(int n)
    {
        int res = 1;
        for (int i = 1; i <= n; i++)
        {
            res = res * 1ll * i % mod;
        }
        return res;
    }
    int C(int n, int k)
    {
        return fact(n) * 1ll * qpow(fact(k), mod - 2) % mod * 1ll * qpow(fact(n - k), mod - 2) % mod;
    }
}
using namespace fastIO;

using namespace std;

int n, m;

signed main()
{
    int _ = 1;
    //input(_);
    while (_--)
    {
        input(n), input(m);
        vector<int> pre(n + 2), nex(n + 2), a(n + 1);
        vector<bool> vis(n + 1, false);
        priority_queue<pair<int, int>> q;
        int i, x;
        for1n(i, n)
        {
            cin >> a[i];
            pre[i] = i - 1;
            nex[i] = i + 1;
            q.push({a[i], i});
        }
        pre[n + 1] = n, nex[0] = 1;
        int ans = 0;
        while (m--)
        {
            while (vis[q.top().second])
                q.pop();
            pair<int, int> t = q.top();
            q.pop();
            if (t.first < 0)
                break;
            ans += t.first;
            x = t.second;
            a[x] = a[pre[x]] + a[nex[x]] - a[x];
            vis[pre[x]] = vis[nex[x]] = true;
            pre[x] = pre[pre[x]], nex[pre[x]] = x;
            nex[x] = nex[nex[x]], pre[nex[x]] = x;
            q.push({a[x], x});
        }
        cout << ans;
    }

    return 0;
}

二、 ICPC2021昆明站A题AC.
该题主要要从题意抽象出反悔贪心的模型，同时利用按位异或的性质来构造结果字符串，其中要注意我们抽象出来的模型，要处理出其代价最小的结果，而不同于上题种树的最大值。
AC代码：

/*
 * @Author: csc
 * @Date: 2021-04-08 23:20:34
 * @LastEditTime: 2021-04-09 00:26:15
 * @LastEditors: Please set LastEditors
 * @Description: In User Settings Edit
 * @FilePath: code_formalniucowicpc_21_km_A.cpp
 */
#include <bits/stdc++.h>
#define pr printf
#define sc scanf
#define sf(n) scanf("%d", &n)
#define sff(n1, n2) scanf("%d %d", &n1, &n2)
#define sfff(n1, n2, n3) scanf("%d %d %d", &n1, &n2, &n3)
#define sl(n) scanf("%lld", &n)
#define sll(n1, n2) scanf("%lld %lld", &n1, &n2)
#define slll(n1, n2, n3) scanf("%lld %lld %lld", &n1, &n2, &n3)
#define for0(i, n) for (i = 0; i < n; i++)
#define for1n(i, n) for (i = 1; i <= n; i++)
#define forab(i, a, b) for (i = a; i <= b; i++)
#define forba(i, a, b) for (i = b; i >= a; i--)
#define pb push_back
#define fi first
#define se second
#define int long long
#define endl 'n'
#define vi vector<int>
#define vii vector<vector<int>>
#define pt pair<int, int>
#define mem(ara, n) memset(ara, n, sizeof(ara))
#define memb(ara) memset(ara, false, sizeof(ara))
#define all(x) (x).begin(), (x).end()
#define sq(x) ((x) * (x))
#define sz(x) x.size()
const int N = 1e6 + 100;
const int mod = 1e9 + 7;
namespace fastIO
{
    inline void input(int &res)
    {
        char c = getchar();
        res = 0;
        int f = 1;
        while (!isdigit(c))
        {
            f ^= c == '-';
            c = getchar();
        }
        while (isdigit(c))
        {
            res = (res << 3) + (res << 1) + (c ^ 48);
            c = getchar();
        }
        res = f ? res : -res;
    }
    inline int qpow(int a, int b)
    {
        int ans = 1, base = a;
        while (b)
        {
            if (b & 1)
                ans = (ans * base % mod + mod) % mod;
            base = (base * base % mod + mod) % mod;
            b >>= 1;
        }
        return ans;
    }
    int fact(int n)
    {
        int res = 1;
        for (int i = 1; i <= n; i++)
        {
            res = res * 1ll * i % mod;
        }
        return res;
    }
    int C(int n, int k)
    {
        return fact(n) * 1ll * qpow(fact(k), mod - 2) % mod * 1ll * qpow(fact(n - k), mod - 2) % mod;
    }
}
using namespace fastIO;
 
using namespace std;
 
int n, k;
char s[N];
bool vis[N];
int v[N], L[N], R[N];
 
struct data
{
    int l, r, val;
} a[N];
 
priority_queue<pt, vector<pt>, greater<pt>> q;
 
signed main()
{
    int _ = 1;
    //input(_);
    while (_--)
    {
        input(n), input(k);
        int ans = 0, sum = 0, i;
        sc("%s", s + 1);
 
        forab(i, 1, n - 1)
        {
            a[i].val = (s[i] != 'a') + (s[i + 1] != 'c');
            a[i].l = i - 1, a[i].r = i + 1;
            L[i] = R[i] = i;
            q.push({a[i].val, i});
        }
        a[0].val = a[n].val = 1e9;
 
        forab(i, 1, n / 2)
        {
            while (vis[q.top().second])
                q.pop();
            pt p = q.top();
            q.pop();
            sum += p.first;
 
            if (sum <= k)
                ans = i;
            else
                break;
 
            v[L[p.second]] ^= 1, v[R[p.second] + 1] ^= 1;
            L[p.second] = L[a[p.second].l];
            R[p.second] = R[a[p.second].r];

            vis[a[p.second].l] = vis[a[p.second].r] = 1;
            a[p.second].val = a[a[p.second].l].val + a[a[p.second].r].val - a[p.second].val;
            a[p.second].l = a[a[p.second].l].l,a[a[p.second].l].r = p.second;
            a[p.second].r = a[a[p.second].r].r,a[a[p.second].r].l = p.second;
            q.push({a[p.second].val, p.second});   
        }
        pr("%lldn", ans);
        forab(i, 1, n)
        {
            v[i] ^= v[i - 1];
            if (v[i])
                s[i] = 'a', s[i + 1] = 'c';
        }
        cout << s + 1 << endl;
    }
 
    return 0;
}