5249: [2018多省省隊聯(lián)測]IIIDX

Time Limit: 40 Sec??Memory Limit: 512 MB
Submit: 32??Solved: 17
[Submit][Status][Discuss]

Description

【題目背景】 Osu聽過沒？那是Konano最喜歡的一款音樂游戲，而他的夢想就是有一天自己也能做個獨特酷炫的音樂游戲。現(xiàn)在 ，他在世界知名游戲公司KONMAI內(nèi)工作，離他的夢想也越來越近了。這款音樂游戲內(nèi)一般都包含了許多歌曲，歌曲 越多，玩家越不易玩膩。同時，為了使玩家在游戲上氪更多的金錢花更多的時間，游戲一開始一般都不會將所有曲 目公開，有些曲目你需要通關(guān)某首特定歌曲才會解鎖，而且越晚解鎖的曲目難度越高。 【題目描述】 這一天，Konano接到了一個任務(wù)，他需要給正在制作中的游戲《IIIDX》安排曲目的解鎖順序。游戲內(nèi)共有n首曲目 ，每首曲目都會有一個難度d，游戲內(nèi)第i首曲目會在玩家Pass第trunc(i/k)首曲目后解鎖（x為下取整符號）若tru nc(i/k)=0，則說明這首曲目無需解鎖。舉個例子：當(dāng)k=2時，第1首曲目是無需解鎖的（trunc(1/2)=0），第7首曲 目需要玩家Pass第trunc(7/2)=3首曲目才會被解鎖。Konano的工作，便是安排這些曲目的順序，使得每次解鎖出的 曲子的難度不低于作為條件需要玩家通關(guān)的曲子的難度，即使得確定順序后的曲目的難度對于每個i滿足Di≥Dtrun c(i/k)。當(dāng)然這難不倒曾經(jīng)在信息學(xué)競賽摸魚許久的Konano。那假如是你，你會怎么解決這份任務(wù)呢

Input

第1行1個正整數(shù)n和1個小數(shù)k，n表示曲目數(shù)量，k其含義如題所示。 第2行n個用空格隔開的正整數(shù)d，表示這n首曲目的難度。 1 ≤ n ≤ 500000 1 < k ≤ 10^9 1 < d ≤ 10^9

Output

輸出1行n個整數(shù)，按順序輸出安排完曲目順序后第i首曲目的難度。 若有多解，則輸出d1最大的；若仍有多解，則輸出d2最大的，以此類推。

Sample Input

4 2.0
114 514 1919 810

Sample Output

114 810 514 1919

HINT

Source

[Submit][Status][Discuss]

首先有一個顯然的貪心，把樹建出來然后后序遍歷從大到小填數(shù)即可。

但是這樣在有重復(fù)數(shù)字的情況下是不行的，如：

?4 2

1 1 1 2

這樣貪心答案是1 1 1 2，但正確答案是1 1 2 1。

這就需要對每個數(shù)進(jìn)行“預(yù)訂”操作。考慮將數(shù)從小到大填進(jìn)樹里，顯然當(dāng)前可能填進(jìn)的節(jié)點一定與已經(jīng)填過的節(jié)點相鄰，所以我們把這些節(jié)點子樹都“預(yù)訂”好，然后找到最靠后的，且不造成上面那個錯誤的節(jié)點填入，最終整棵樹就填好了。

具體實現(xiàn)很難講清楚，還是看代碼吧。

1 #include <cmath> 2 #include <cstdio> 3 #include <algorithm> 4 #define N 500010 5 #define lson l ,mid ,x << 1 6 #define rson mid + 1 ,r ,x << 1 | 1 7 #define rep(i,l,r) for (int i=l; i<=r; i++) 8 using namespace std; 9 int a[N] ,ans[N] ,head[N] ,to[N] ,nxt[N] ,cnt ,si[N] ,sum[N << 2]; 10 11 void add(int x ,int y){ to[++cnt] = y ,nxt[cnt] = head[x] ,head[x] = cnt ,si[x] += si[y]; } 12 13 void update(int p ,int a ,int l ,int r ,int x){ 14 sum[x] += a; 15 if(l == r) return; 16 int mid = (l + r) >> 1; 17 if(p <= mid) update(p ,a ,lson); 18 else update(p ,a ,rson); 19 } 20 21 int find(int k ,int l ,int r ,int x){ 22 if(l == r) return l; 23 int mid = (l + r) >> 1; 24 if(sum[x << 1 | 1] < k) return find(k - sum[x << 1 | 1] ,lson); 25 else return find(k ,rson); 26 } 27 28 int main(){ 29 int n ,i ,j ,t ,l ,last = 1; 30 double k; scanf("%d%lf" ,&n ,&k); 31 rep(i,1,n) scanf("%d" ,&a[i]) ,si[i] = 1; 32 sort(a + 1 ,a + n + 1); 33 for(i = n ; i ; i -- ) add((int)floor(i / k) ,i); 34 for(i = head[0] ; i ; i = nxt[i]) update(to[i] ,si[to[i]] ,1 ,n ,1); 35 for(i = 1 ; i <= n ; i = last){ 36 while(last <= n && a[i] == a[last]) last ++ ; 37 for(j = last - i ; j ; j -- ){ 38 t = find(j ,1 ,n ,1) ,ans[t] = a[i] ,update(t ,-si[t] ,1 ,n ,1); 39 for(l = head[t] ; l ; l = nxt[l]) update(to[l] ,si[to[l]] ,1 ,n ,1); 40 } 41 } 42 rep(i,1,n) printf("%d " ,ans[i]); 43 return 0; 44 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/HocRiser/p/8742680.html

總結(jié)

以上是生活随笔為你收集整理的[BZOJ5249][九省联考2018]IIIDX(线段树)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。