【刷题】BZOJ 2151 种树

时间:2024-01-20 19:36:03

Description

A城市有一个巨大的圆形广场,为了绿化环境和净化空气,市*决定沿圆形广场外圈种一圈树。园林部门得到指令后,初步规划出n个种树的位置,顺时针编号1到n。并且每个位置都有一个美观度Ai,如果在这里种树就可以得到这Ai的美观度。但由于A城市土壤肥力欠佳,两棵树决不能种在相邻的位置(i号位置和i+1号位置叫相邻位置。值得注意的是1号和n号也算相邻位置!)。最终市*给园林部门提供了m棵树苗并要求全部种上,请你帮忙设计种树方案使得美观度总和最大。如果无法将m棵树苗全部种上,给出无解信息。

Input

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

Output

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

Sample Input

【样例输入1】

7 3

1 2 3 4 5 6 7

【样例输入2】

7 4

1 2 3 4 5 6 7

Sample Output

【样例输出1】

15

【样例输出2】

Error!

【数据规模】

对于全部数据:m<=n;

-1000<=Ai<=1000

N的大小对于不同数据有所不同:

数据编号 N的大小 数据编号 N的大小

1 30 11 200

2 35 12 2007

3 40 13 2008

4 45 14 2009

5 50 15 2010

6 55 16 2011

7 60 17 2012

8 65 18 199999

9 200 19 199999

10 200 20 200000

Solution

贪心题

把整个环用双向链表串起来

每次贪心选择价值最大的位置 \(x\)

用 \(V[nxt[x]]+V[pre[x]]-V[x]\) 替代,它删去 \(pre[x]\) 和 \(nxt[x]\)

#include<bits/stdc++.h>
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN=200000+10;
int n,m,ans;
struct node{
int id,val,pre,nxt;
inline bool operator < (const node &A) const {
return val>A.val||(val==A.val&&id<A.id);
};
};
node tree[MAXN];
std::set<node> S;
template<typename T> inline void read(T &x)
{
T data=0,w=1;
char ch=0;
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();
x=data*w;
}
template<typename T> inline void write(T x,char ch='\0')
{
if(x<0)putchar('-'),x=-x;
if(x>9)write(x/10);
putchar(x%10+'0');
if(ch!='\0')putchar(ch);
}
template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);}
template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);}
template<typename T> inline T min(T x,T y){return x<y?x:y;}
template<typename T> inline T max(T x,T y){return x>y?x:y;}
int main()
{
read(n);read(m);
if(n<(m<<1))
{
puts("Error!");
return 0;
}
for(register int i=1,x;i<=n;++i)read(x),S.insert(tree[i]=(node){i,x,i==1?n:i-1,i==n?1:i+1});
while(m--)
{
node now=*S.begin(),l=tree[now.pre],r=tree[now.nxt],pl=tree[l.pre],pr=tree[r.nxt];
S.erase(now);S.erase(l);S.erase(r);S.erase(pl);S.erase(pr);
ans+=now.val;
now.val=l.val+r.val-now.val;
now.pre=pl.id,now.nxt=pr.id;
pl.nxt=now.id,pr.pre=now.id;
tree[now.id]=now;tree[pl.id]=pl;tree[pr.id]=pr;
S.insert(now);S.insert(pl);S.insert(pr);
}
write(ans,'\n');
return 0;
}