本文主要是介绍Arrangement for Contests UVALive - 8519，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
贪心的思想 线段树操作
每次取区间最小值 然后拿掉这个最小值 并不影响区间内非最小值的匹配
#include <bits/stdc++.h>
using namespace std;
#define N 0x3f3f3f3fstruct node1
{int l;int r;int minn;int pos;int laz;
};struct node2
{int minn;int pos;
};node1 tree[400010];
int n,p;void pushup(int cur)
{if(tree[2*cur].minn<tree[2*cur+1].minn){tree[cur].minn=tree[2*cur].minn;tree[cur].pos=tree[2*cur].pos;}else{tree[cur].minn=tree[2*cur+1].minn;tree[cur].pos=tree[2*cur+1].pos;}return;
}void pushdown(int cur)
{if(tree[cur].laz!=0){tree[2*cur].minn-=tree[cur].laz;tree[2*cur].laz+=tree[cur].laz;tree[2*cur+1].minn-=tree[cur].laz;tree[2*cur+1].laz+=tree[cur].laz;tree[cur].laz=0;}return;
}void build(int l,int r,int cur)
{int m;tree[cur].l=l;tree[cur].r=r;tree[cur].minn=N;tree[cur].pos=-1;tree[cur].laz=0;if(l==r){scanf("%d",&tree[cur].minn);tree[cur].pos=l;return;}m=(l+r)/2;build(l,m,2*cur);build(m+1,r,2*cur+1);pushup(cur);return;
}node2 query(int pl,int pr,int cur)
{node2 res,tem;if(pl<=tree[cur].l&&tree[cur].r<=pr){res.minn=tree[cur].minn;res.pos=tree[cur].pos;return res;}res.minn=N,res.pos=-1;if(pl<=tree[2*cur].r){tem=query(pl,pr,2*cur);if(res.minn>tem.minn) res=tem;}if(pr>=tree[2*cur+1].l){tem=query(pl,pr,2*cur+1);if(res.minn>tem.minn) res=tem;}return res;
}void update(int pl,int pr,int val,int cur)
{if(pl<=tree[cur].l&&tree[cur].r<=pr){tree[cur].minn-=val;tree[cur].laz+=val;return;}pushdown(cur);if(pl<=tree[2*cur].r) update(pl,pr,val,2*cur);if(pr>=tree[2*cur+1].l) update(pl,pr,val,2*cur+1);pushup(cur);return;
}int main()
{node2 tem;int t,k,ans;scanf("%d",&t);while(t--){scanf("%d%d",&n,&k);build(1,n,1);ans=0;p=1;while(p+k-1<=n){tem=query(p,p+k-1,1);ans+=tem.minn;update(p,p+k-1,tem.minn,1);p=tem.pos+1;}printf("%d\n",ans);}return 0;
}
这篇关于Arrangement for Contests UVALive - 8519的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
