【算法】贪心+堆

【题意】n个数字的序列，要求选择互不相邻的k个数字使和最大。

【题解】

贪心，就是按一定顺序选取即可最优，不会反悔。

考虑第一个数字选择权值最大的，那么它相邻的两个数字就不能选择，那么我们可以把这三个数字视为一个整体。操作为将pre[pre[x]]和x和suc[suc[x]]连接起来。

由于可能依然有选择相邻两个数字的可能性，将中间的权值置为A[pre[x]]+A[suc[x]]-A[x]，这个权值记录在中间，但实际上代表相邻三个数字的新权值。

若再次选择这个区间，那么就是把区间更新到周围五个数字了(这里的数字有可能已经是一段区间)，如此可以不断扩大。

 

贪心原理：若没有间隔种的限制，每次都取大就是最优的。那么多了这个限制之后，取大依然优但却会影响旁边两个数字的选择。

为了使我们依然能贪心，就设置一个反悔的机会，即设置一个新权值。那么如果非要选择旁边两个就相当于选择中间的权值两次，每次把影响区间扩大2并视之为一个数字。

因为贪心就不会反悔的性质，既然会选择这个决策就一定不会悔改。这个反悔的机会实质上是扩大你选择数字的影响范围，一旦扩大就一定不会反悔，因为一定是最优的。

 

每次出现新权值用堆维护。记得开始先特判无法种k棵的情况，因为后面很难判断。

#include
      
       #include
       
        #include
        
         #include
         
          using namespace std;const int maxn=200010;struct cyc{    int num,ord;    bool operator < (const cyc &x)const    {
     return num
          
           
            q;int a[maxn],pre[maxn],suc[maxn],n,k;bool f[maxn];void del(int x){ f[x]=1; suc[pre[x]]=suc[x]; pre[suc[x]]=pre[x]; suc[x]=pre[x]=0;}int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); q.push((cyc){a[i],i}); pre[i]=i-1;suc[i]=i+1; } pre[1]=n;suc[n]=1; int ans=0; if(k>n/2){printf("Error!");return 0;} for(int i=1;i<=k;i++) { while(f[q.top().ord])q.pop(); qp=q.top();q.pop(); ans+=qp.num; int A=pre[qp.ord],B=suc[qp.ord]; a[qp.ord]=a[A]+a[B]-qp.num; del(pre[qp.ord]);del(suc[qp.ord]); q.push((cyc){a[qp.ord],qp.ord}); } printf("%d",ans); return 0;}