Description

經過三十多個小時的長途跋涉，小Z和小D終于到了NOI現場——南山南中學。一進校園，小D就被花所吸引了（不要問我為什么），遍和一旁的種花園丁交（J）流（L）了起來。
他發現花的擺放竟有如此奧秘：圓形廣場共有 N 個種花的位置，順時針編號1到N。并且每個位置都有一個美觀度ai ，如果在這里種花就可以得到這ai 的美觀度。但由于地處南山土壤肥力欠佳，兩株花不能種在相鄰的位置（1號和N號也算相鄰位置）。校方一共給了 M 株花，經過園丁的精妙擺放，才能如此吸引小D。所以現在小D也想知道應該如何擺這 N 株花。

Input

輸入第一行包含兩個整數N,M 。
接下來一行包含N個正整數，依次描述美觀度a1,a2,…,an 。

Output

輸出一個整數，表示最佳植樹方案可以得到的美觀度。如果無解輸出“Error!”，不包含引號。

Sample Input

7 3
1 2 3 4 5 6 7

Sample Output

15

Data Constraint

對于50%的數據滿足N<=3000 。
對于100%的數據滿足M<=N<=200000 ，-1000<=ai<=1000 。

Solution

-這題的解法是——貪心+堆。

• 以 A[i] 為關鍵字建大根堆，用一個鏈表存放當前物品。

• 最初鏈表中元素是 1?N，i 的后繼是 i+1，前驅是 i?1 。

• （當然，特別的，1 的前驅是 N，N 的后繼是 1）。

• 執行 M 次操作，每一次操作都將堆頂元素 k 取出，ans+=A[k] 。

• 然后在鏈表中刪除 k 的前驅 pre 和后繼 nxt，令 A[k]=A[pre]+A[nxt]?A[k] ，并更新堆。

• 時間復雜度 O(MlogN)

Code

#include<cstdio> #include<queue> using namespace std; const int N=200001; int ans; int a[N],l[N],r[N]; bool bz[N]; struct data {int x;friend bool operator <(const data x,const data y){return a[x.x]<a[y.x];} }t; priority_queue<data>q; inline int read() {int X=0,w=1; char ch=0;while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();return X*w; } int main() {int n=read(),m=read();if(m>n>>1){printf("Error!");return 0;}for(int i=1;i<=n;i++){a[t.x=i]=read();l[i]=i==1?n:i-1;r[i]=i==n?1:i+1;q.push(t);}while(m--){for(t=q.top(),q.pop();bz[t.x];t=q.top(),q.pop());ans+=a[t.x];a[t.x]=a[l[t.x]]+a[r[t.x]]-a[t.x];bz[l[t.x]]=bz[r[t.x]]=true;l[t.x]=l[l[t.x]];r[t.x]=r[r[t.x]];l[r[t.x]]=r[l[t.x]]=t.x;q.push(t);}printf("%d",ans);return 0; }

總結

以上是生活随笔為你收集整理的JZOJ 4726. 【NOIP2016提高A组模拟8.22】种花的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。