非常神的一道题.
Code:
#include<bits/stdc++.h> #define setIO(s) freopen(s".in","r",stdin) #define maxn 1000000 #define inf 100000000000 using namespace std; struct Node{ long long key; int id; Node(long long a=0,int b=0):key(a),id(b){} bool operator < ( Node c) const{ return key > c.key; } }; priority_queue<Node>Q; int tag[maxn],suf[maxn],pre[maxn]; long long h[maxn],arr[maxn]; int main(){ // setIO("input"); int n,k; scanf("%d%d",&n,&k); for(int i=1;i<=n;++i) scanf("%lld",&arr[i]); for(int i=1;i<=n;++i) { h[i]=(long long) arr[i]-arr[i-1], suf[i]=i+1,pre[i]=i-1; } h[0]=inf, suf[n]=pre[2]=0; for(int i=2;i<=n;++i) Q.push(Node(h[i],i)); long long ans = 0; for(int i=1;i<=k;++i) { while(tag[Q.top().id]) Q.pop(); Node u = Q.top(); ans += (long long) u.key; int cur = u.id; int l = pre[cur],r = suf[cur]; h[cur] = h[l]+h[r]-h[cur]; tag[l]=tag[r]=1; h[l]=h[r]=inf; pre[cur]=pre[l],suf[pre[cur]] = cur; suf[cur]=suf[r],pre[suf[r]] = cur; Q.pop(); Q.push(Node(h[cur],cur)); } printf("%lld",ans); return 0; }posted @ 2019-05-22 10:28 EM-LGH 阅读( ...) 评论( ...) 编辑 收藏
