博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
2018 省选 D1T2 IIIDX
阅读量:5940 次
发布时间:2019-06-19

本文共 2377 字,大约阅读时间需要 7 分钟。

题目大意:

给出k、n个数选择一种字典序最大的排列,使得对于任意的i,di>=d[i/k](下取整 下同)

分析:

很容易想到的是建树,将i的父亲设为[i/k],之后建有向边。

60分贪心:

将原先的a数组升序排列,直接根据子树大小分配排位。pai[i]=(同层级剩余的)-(子树大小)+1; 然而对于di有相同的情况时,也许可能会使得子树之间值发生交换,仍使得命题成立。

例如: [1,2,2,3] k=2;

正解:[1,2,3,2]

贪心: [1,2,2,3]

问题在于,因为题目中说了满足单调不降即可,而贪心则极力向后取数,可能会将大的数预留给自己较大编号的后代。如这个例子中,2号取到了3号排位,将4号排位、最大的3留给了4号。而3号就只剩下了2号排位。

我们想最大化较小的编号的值,就让它尽量往后取排位。 但是由于单调不降,可以让2号取2号位,4号取3号位,3号取4号位。使得答案更优。

正解:

线段树。

令原数组a降序排列。 令f[i]表示i号排位左边还有几个位置上的数是可以取到的。线段树维护这个区间内f的最小值。

显然这个f数组单调不降。对于从小到大的第i个编号,我们每次二分一个x,使得找到一个最靠左的位置,使得f[x]>=size[i],若有多个x,找到最靠右的一个x(这样使得在x取值最优时,尽可能将大的数留给后面的数。)让[x~n]区间上的值都减去size[i]

具体实现:

1.先判断到了i号点时,有没有进入下一个层级,如果有,将上一个层级预留的值都加回来(+size[fa]-1),才能二分、利用。

2.二分找到一个p;将p移动到同一个数值的、未用过的最右边。

3.将p赋值给ans[i],记录该p已经被用过(详见代码中nxt[p]++,这样保证下次减回来能多减一个位置

4.给子树预留位置。

详见代码:

#include
#include
#include
#include
#include
using namespace std;const int N=500000+10;int nxt[N],a[N],ans[N],fa[N],size[N];int n;double k;struct node{ int mi,l,r; int add; #define mix t[x].mi #define lx t[x].l #define rx t[x].r #define lsx x<<1 #define rsx x<<1|1 #define ax t[x].add #define milsx t[lsx].mi #define mirsx t[rsx].mi #define alsx t[x<<1].add #define arsx t[x<<1|1].add}t[N<<2];void push(int x){ if(!ax) return; milsx+=ax; mirsx+=ax; alsx+=ax; arsx+=ax; ax=0;}void build(int l,int r,int x){ if(l==r) { mix=l,lx=l,rx=r;ax=0;return; } int mid=(l+r)>>1; lx=l,rx=r,ax=0; build(l,mid,lsx); build(mid+1,r,rsx); mix=min(mirsx,milsx);}void add(int l,int r,int x,int c){ if(l<=lx&&rx<=r) { mix+=c; ax+=c;return; } push(x); int mid=(lx+rx)>>1; if(l<=mid) add(l,r,lsx,c); if(mid
b;}void prework(){ sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++) fa[i]=int(i/k),size[i]=1; for(int i=n-1;i;i--) if(a[i]==a[i+1]) nxt[i]=nxt[i+1]+1; for(int i=n;i;i--) size[fa[i]]+=size[i];}int main(){ scanf("%d%lf",&n,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); prework(); int root=1; build(1,n,root); for(int i=1;i<=n;i++) { if(fa[i]!=fa[i-1]) add(ans[fa[i]],n,root,size[fa[i]]-1); int p=find(root,size[i]); p+=nxt[p];nxt[p]++;p-=nxt[p]-1;ans[i]=p; add(p,n,root,-size[i]); } for(int i=1;i<=n;i++) printf("%d ",a[ans[i]]); return 0;}

 

转载于:https://www.cnblogs.com/Miracevin/p/9031549.html

你可能感兴趣的文章
常用的正则表达式分享
查看>>
我的世界:一个村落(其一)
查看>>
SKChoosePopView 一个HUD风格的可定制化选项弹窗的快速解决方案
查看>>
(二十)java多线程之ScheduledThreadPoolExecutor
查看>>
【译】码农生涯十六条不要
查看>>
sublime快捷键
查看>>
认识jQuery及jQuery选择器
查看>>
动态密码算法介绍与实现
查看>>
从前后端分离到GraphQL,携程如何用Node实现?\n
查看>>
JavaScript标准库系列——RegExp对象(三)
查看>>
Linux Namespace系列(09):利用Namespace创建一个简单可用的容器
查看>>
js深度解析url地址
查看>>
web入门+书籍推荐
查看>>
[转]:xmake插件开发之色彩高亮显示
查看>>
OS X 下在代码中枚举所有进程的方法
查看>>
eventEmitter3源码分析与学习
查看>>
关于缓存命中率的几个关键问题!
查看>>
罗田用好“大数据”力促扶贫更精准
查看>>
IDC: New H3C集团正式启动——中国企业IT新星时代已然来临
查看>>
易传媒CTO程华奕:搭建私有DMP 你必须知道的几件事
查看>>