ACM模版

描述

题解

首先发一下官方题解吧：

按照官方题解写的代码发现自己一直在第 21 组数据 TLE ，很明显，这组数据是后来加上去专门卡数据的。

于是发现自己的代码中忽略了一个部分是暴力的思维，在查找左右两侧可选的村民时，我用了两个循环，这显然是不行的，所以我需要使用链表的思维，这样查找的复杂度就是 O(1) 了，也就顺利的 AC 了。

代码

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

typedef long long ll;

const int MAXN = 1e5 + 10;

int n;
ll m[MAXN];
int l[MAXN], r[MAXN];
set<pair<ll, int> > spli;

void del(int x)
{
    spli.erase(make_pair(m[x], x));
    r[l[x]] = r[x];
    l[r[x]] = l[x];
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &m[i]);
        spli.insert(make_pair(m[i], i));
        l[(i + 1) % n] = i;
        r[i] = (i + 1) % n;
    }

    int cnt = n / 3;
    ll ans = 0;
    for (int i = 0, j; i < cnt; i++)
    {
        j = spli.rbegin()->second;
        ll a = m[l[j]], b = m[j], c = m[r[j]];

        ans += b;
        del(l[j]);
        del(r[j]);
        spli.erase(make_pair(m[j], j));
        m[j] = a + c - b;
        spli.insert(make_pair(m[j], j));
    }

    cout << ans << endl;

    return 0;
}