贪心 park

来总结一道非常经典的好题

这一道题是通过贪心实现的

首先看到这一题的时间复杂度

n<=100000

需要一个比较玄学的做法

我们先假设把题干改成这个样子

一圈n个车位

停在每个车位都有一定的代价

停m个车可以相邻求最小代价

那么这就是非常简单的贪心

可以每一次都取当前最小的车位来停

那么这个题只不过是增加了一个不能两两相邻的限制条件

我们可以想办法变成上一个题

如果我们有一个环是这样的

y z

这四个数中最小的数是x

然而y+z<x+a

如果我们用普通的贪心肯定是先取到最小的x

那么这一道题得出的就不是正确答案

我们假如要删掉x 选y和z 需要怎么处理呢？

我们可以添加一个值y+z-x点

如果将这个点加到答案里面就相当于对x进行了删除操作并且选上了y和z

注：我们还要证明一下为什么去掉x后如果选y就一定也要选z

y x z

如果我们之前选过了x（最小）现在有更优的解需要删掉x

假如我们只选了y

没有选z

那么这是不成立的

因为如果只选了y 完全可以把y替换成x从而得出一个更小更优的答案

所以如果选了y

就一定也会选z

这一道题的实现方法就是维护一个优先队列

我们先把所有的点入队

这样子就队列内部就自动维护从小到大排序了（堆实现的）

我们每一次取出最前的一个点（当前最小）

累加到ans上并把当前点删除把两边合并

也就是

再把当前点的值变为左+右-自己就是刚才说的

作为一个新的点加入到优先队列里去

如此一来既维护了答案最小也维护了点两两不相邻

这是比较经典且有难度的一个题型要好好掌握！

#include<bits/stdc++.h>
#define N 200010
#define pa pair<int,int>
using namespace std;
int n,m,a[N];
int L[N],R[N];
bool vis[N];
void del(int x)
{
    vis[x]=1;
    R[L[x]]=R[x];
    L[R[x]]=L[x];
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    priority_queue<pa,vector<pa>,greater<pa> >q;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
        if(i==1)
            L[i]=n;
        else
            L[i]=i-1;
        if(i==n) R[i]=1;
        else R[i]=i+1;
        q.push(pa(a[i],i));//优先队列 
    }
    int ans=0;
    while(m--){
        while(vis[q.top().second])
            q.pop();
        int x=q.top().second;
        q.pop();
        ans+=a[x];
        a[x]=a[L[x]]+a[R[x]]-a[x];
        del(L[x]);del(R[x]);
        q.push(pa(a[x],x));
    }
    cout<<ans;
    
    
    
    return 0;
}