文档章节

洛谷P4364 [九省联考2018]IIIDX 【线段树】

o
 osc_z1hvg4cu
发布于 2018/04/24 19:47
字数 1268
阅读 12
收藏 0

精选30+云产品,助力企业轻松上云!>>>

题目

【题目背景】 Osu听过没?那是Konano最喜欢的一款音乐游戏,而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在 ,他在世界知名游戏公司KONMAI内工作,离他的梦想也越来越近了。这款音乐游戏内一般都包含了许多歌曲,歌曲 越多,玩家越不易玩腻。同时,为了使玩家在游戏上氪更多的金钱花更多的时间,游戏一开始一般都不会将所有曲 目公开,有些曲目你需要通关某首特定歌曲才会解锁,而且越晚解锁的曲目难度越高。 【题目描述】 这一天,Konano接到了一个任务,他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n首曲目 ,每首曲目都会有一个难度d,游戏内第i首曲目会在玩家Pass第trunc(i/k)首曲目后解锁(x为下取整符号)若tru nc(i/k)=0,则说明这首曲目无需解锁。举个例子:当k=2时,第1首曲目是无需解锁的(trunc(1/2)=0),第7首曲 目需要玩家Pass第trunc(7/2)=3首曲目才会被解锁。Konano的工作,便是安排这些曲目的顺序,使得每次解锁出的 曲子的难度不低于作为条件需要玩家通关的曲子的难度,即使得确定顺序后的曲目的难度对于每个i满足Di≥Dtrun c(i/k)。当然这难不倒曾经在信息学竞赛摸鱼许久的Konano。那假如是你,你会怎么解决这份任务呢

输入格式

第1行1个正整数n和1个小数k,n表示曲目数量,k其含义如题所示。 第2行n个用空格隔开的正整数d,表示这n首曲目的难度。 1 ≤ n ≤ 500000 1 < k ≤ 10^9 1 < d ≤ 10^9

输出格式

输出1行n个整数,按顺序输出安排完曲目顺序后第i首曲目的难度。 若有多解,则输出d1最大的;若仍有多解,则输出d2最大的,以此类推。

输入样例

4 2.0

114 514 1919 810

输出样例

114 810 514 1919

题解

太神了,,orz

有一个很明显的错误贪心就不多说了 直接讲正解

将权值降序排序 建立一个线段树维护一个数组$pre[i]$,表示$i$号权值之前有几个位置可选,初始化$pre[i] = i$ 我们从$1$号点顺序访问每个点,在线段树上二分查找右侧$pre[]$都大于$siz[u]$的位置,然后找到该位置的最右相同权值的位置$pos$,赋给当前点 然后我们为了给其子树留够$siz[u] - 1$个值【同时减去已经用掉的一个值】,我们将区间$[pos,n]$减去$siz[u]$,这样就保证了外面的点选完之后一定会给子树内的点留够那么多之前的权值

我们访问到一个点时,如果该点有父亲,那么要撤销掉父亲的预留操作【但多个儿子只撤销一次】

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
const int maxn = 500005,maxm = 100005,INF = 1000000000;
inline int read(){
	int out = 0,flag = 1; char c = getchar();
	while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
	while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
	return out * flag;
}
double K;
int n,siz[maxn],cnt[maxn],fa[maxn],val[maxn],rel[maxn],ans[maxn];
int mn[maxn << 2],tag[maxn << 2];
void upd(int u){mn[u] = min(mn[ls],mn[rs]);}
void pd(int u){
	if (tag[u] != 0){
		mn[ls] += tag[u]; tag[ls] += tag[u];
		mn[rs] += tag[u]; tag[rs] += tag[u];
		tag[u] = 0;
	}
}
void build(int u,int l,int r){
	if (l == r){
		mn[u] = l;
		return;
	}
	int mid = l + r >> 1;
	build(ls,l,mid);
	build(rs,mid + 1,r);
	upd(u);
}
void modify(int u,int l,int r,int L,int R,int v){
	if (l >= L && r <= R) {
		mn[u] += v; tag[u] += v;
		return;
	}
	pd(u);
	int mid = l + r >> 1;
	if (mid >= L) modify(ls,l,mid,L,R,v);
	if (mid < R) modify(rs,mid + 1,r,L,R,v);
	upd(u);
}
int query(int u,int l,int r,int v){
	if (l == r) return mn[u] >= v ? l : l + 1;
	pd(u);
	int mid = l + r >> 1;
	if (mn[rs] >= v) return query(ls,l,mid,v);
	return query(rs,mid + 1,r,v);
}
inline bool cmp(const int& a,const int& b){
	return a > b;
}
int main(){
	n = read(); scanf("%lf",&K);
	REP(i,n) val[i] = read();
	REP(i,n) fa[i] = (int)floor(i / K);
	for (int i = n; i; i--){
		siz[i]++;
		siz[fa[i]] += siz[i];
	}
	sort(val + 1,val + 1 + n,cmp);
	for (int i = n; i; i--){
		if (i == n || val[i] != val[i + 1]) cnt[i] = 1;
		else cnt[i] = cnt[i + 1] + 1;
	}
	build(1,1,n);
	for (int i = 1; i <= n; i++){
		if (fa[i] && !rel[fa[i]]){
			rel[fa[i]] = true;
			modify(1,1,n,ans[fa[i]],n,siz[fa[i]] - 1);
		}
		int p = query(1,1,n,siz[i]),u;
		u = p + cnt[p] - 1; cnt[p]--;
		ans[i] = u;
		modify(1,1,n,u,n,-siz[i]);
	}
	REP(i,n) printf("%d ",val[ans[i]]);
	return 0;
}

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

dict.items()和dict.iteritems()有什么区别?

问题: Are there any applicable differences between dict.items() and dict.iteritems() ? dict.items()和dict.iteritems()之间是否有适用的区别? From the Python docs: 从Python文档中......

法国红酒甜
今天
20
0
R中“ =”和“ <-”赋值运算符有什么区别?

问题: What are the differences between the assignment operators = and <- in R? R中赋值运算符=和<-之间有什么区别? I know that operators are slightly different, as this example ......

fyin1314
今天
20
0
之间的区别 和

问题: I'm learning Spring 3 and I don't seem to grasp the functionality behind <context:annotation-config> and <context:component-scan> . 我正在学习Spring 3,并且似乎不太了解<......

javail
今天
15
0
业内首款,百度工业视觉智能平台全新亮相

本文作者:y****n 业内首款全国产化工业视觉智能平台——百度工业视觉智能平台亮相中国机器视觉展(Vision China),该平台所具有的核心AI能力完全自主可控,在质检、巡检等场景中具有高效、...

百度开发者中心
昨天
7
0
我们如何制作xkcd样式图? - How can we make xkcd style graphs?

问题: Apparently, folk have figured out how to make xkcd style graphs in Mathematica and in LaTeX . 显然,民间已经想出了如何在Mathematica和LaTeX中制作xkcd风格的图形。 Can we d......

富含淀粉
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部