题目描述

A城市有一个巨大的圆形广场，为了绿化环境和净化空气，市政府决定沿圆形广场外圈种一圈树。

园林部门得到指令后，初步规划出n个种树的位置，顺时针编号1到n。并且每个位置都有一个美观度Ai，如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳，两棵树决不能种在相邻的位置（i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置！）。

最终市政府给园林部门提供了m棵树苗并要求全部种上，请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上，给出无解信息。

输入输出格式

输入格式：

输入的第一行包含两个正整数n、m。第二行n个整数Ai。

输出格式：

输出一个整数，表示最佳植树方案可以得到的美观度。如果无解输出“Error!”，不包含引号。

输入输出样例

输入样例#1：

7 3

1 2 3 4 5 6 7

输出样例#1：

15

输入样例#2：

7 4

1 2 3 4 5 6 7

输出样例#2：

Error!

说明

对于全部数据：m<=n；

-1000<=Ai<=1000

刚看到这题第一反应是DP。。然而瞅了一眼数据范围（emm,200000）

发现是一个贪心。。思路非常神奇。。

就是以在每个坑种树的收益建一个大根堆

然后用链表存它的前驱后继（n的后继为1,1的前驱为n）

每次取最大的收益。

那么问题来了————有可能在这个点种树比在它两边各种一棵树收益小。

但一定是两边各种一棵，因为我们建的是大根堆，先出来的一定大。

所以我们可以选这个坑种树，也可以选两边的坑各种一棵，所以我们给我们的贪心一个反悔的机会

就是选在这个坑种树以后将它两边的坑合并为一个价值为（w[l]+w[r]-w[now]）的坑，代替我们选择的坑

这里非常的巧妙，就是如果选了这个坑就相当于不在那个中间的坑种树了，而是在它两边各种一棵。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          # define M (200000+50)using namespace std;struct node{ int value,place; friend bool operator < (node x,node y){ return x.value < y.value; }};priority_queue
          
            q;int n,m,Ans,chose,nxt[M],pre[M],w[M],l,r;bool vis[M];void change(int x){ vis[x]=1; nxt[pre[x]]=nxt[x]; pre[nxt[x]]=pre[x]; nxt[x]=0; pre[x]=0;}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&w[i]); } if((n>>1)