【題目背景】
Osu聽過沒？那是Konano最喜歡的一款音樂游戲，而他的夢想就是有一天自己也能做個獨特酷炫的音樂游戲。現在
，他在世界知名游戲公司KONMAI內工作，離他的夢想也越來越近了。這款音樂游戲內一般都包含了許多歌曲，歌曲
越多，玩家越不易玩膩。同時，為了使玩家在游戲上氪更多的金錢花更多的時間，游戲一開始一般都不會將所有曲
目公開，有些曲目你需要通關某首特定歌曲才會解鎖，而且越晚解鎖的曲目難度越高。
【題目描述】
這一天，Konano接到了一個任務，他需要給正在制作中的游戲《IIIDX》安排曲目的解鎖順序。游戲內共有n首曲目，每首曲目都會有一個難度d，游戲內第i首曲目會在玩家Pass第trunc(i/k)首曲目后解鎖（x為下取整符號）若trunc(i/k)=0，則說明這首曲目無需解鎖。舉個例子：當k=2時，第1首曲目是無需解鎖（trunc(1/2)=0），第7首曲目需要玩家Pass第trunc(7/2)=3首曲目才會被解鎖。Konano的工作，便是安排這些曲目的順序，使得每次解鎖出的曲子的難度不低于作為條件需要玩家通關的曲子的難度，即使得確定順序后的曲目的難度對于每個i滿足Di≥Dtrunc(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
Output
輸出1行n個整數，按順序輸出安排完曲目順序后第i首曲目的難度。
若有多解，則輸出d1最大的；若仍有多解，則輸出d2最大的，以此類推。
4 2.0
114 514 1919 810
Sample Output
114 810 514 1919
60pts的做法比較好想
就是把d按從大到小排個序
然后每到一個點i,把最大的size[i]個權值拿出來分配給它及它的子樹
但是這樣并不能處理d不同的情況
所以正解是一種肥腸NB的做法(我顯然不會)
就是先把d按照從大到小排個序
還是求出每個點的size
然后用線段樹維護tmin[i]
tmin[i]表示每個權值左邊(就是比ta大的權值)還有多少能選
其實和60pts的思路有點相似
取一個點肯定就是盡量取大的
那么就使用第size大的
當取一個點的權值后,要給ta的子樹占權值
所以就選和第size大的權值相同且位置最靠右的權值(從左向右滿足不上升==)
這樣能為ta的子樹占到更大的權值
這些權值都在ta的左邊(>=ta的權值)
所以就把ta的右邊的tmin都減掉size
還有一點就是當更新到一個有父親的點的時候
把ta父親給ta占的點都加回來(但只能加一次)
#include<cstdio>
#include<cstring>
#include<algorithm>
# define ls now<<1
# define rs now<<1|1··
const int M = 500005 ;
using namespace std ;
inline int read() {char c = getchar() ; int x = 0 , w = 1 ;while(c>'9'||c<'0') { if(c=='-') w = -1 ; c = getchar() ; }while(c>='0'&&c<='9') { x = x*10+c-'0' ; c = getchar() ; }return x*w ;
}
double k ;
bool vis[M] ;
int n , d[M] , size[M] , fa[M] , tmin[M<<2] , tag[M<<2] , p[M] , cnt[M] ;
inline bool Cmp(int a , int b) { return a > b ; }
inline void pushup(int now){tmin[now] = min(tmin[ls] , tmin[rs]) ;
}
void Build(int l , int r , int now) {if(l == r) {tmin[now] = l ;return ;}int mid = (l + r)>>1 ;Build(l , mid , ls) ; Build(mid + 1 , r , rs) ;pushup(now) ;
}
inline void pushdown(int now) {if(tag[now]) {tmin[ls] += tag[now] ; tmin[rs] += tag[now] ;tag[ls] += tag[now] ; tag[rs] += tag[now] ;tag[now] = 0 ;}
}
void Change(int L , int R , int val , int l , int r , int now) {if(l > R || r < L) return ;if(l == L && r == R) {tmin[now] += val ;tag[now] += val ; return ;}int mid = (l + r)>>1 ;pushdown(now) ;if(mid >= R) Change(L , R , val , l , mid , ls) ;else if(mid < L) Change(L , R , val , mid + 1 , r , rs) ;else {Change(L , mid , val , l , mid , ls) ;Change(mid + 1 , R , val , mid + 1 , r , rs) ;}pushup(now) ;
}
int query(int l , int r , int x , int now) {if(l == r) return tmin[now] >= x ? l : l + 1 ;pushdown(now) ;int mid = (l + r)>>1 ;if(tmin[rs] >= x) return query(l , mid , x , ls) ;else return query(mid + 1 , r , x , rs) ;
}
int main() {scanf("%d%lf",&n,&k) ;for(int i = 1 ; i <= n ; i ++) {d[i] = read() ;size[i] = 1 ;fa[i] = i/k ;}sort(d + 1 , d + n + 1 , Cmp) ;for(int i = n - 1 ; i >= 1 ; i --) if(d[i] == d[i + 1]) cnt[i] = cnt[i + 1] + 1 ;else cnt[i] = 0 ; for(int i = n ; i >= 1 ; i --) size[fa[i]] += size[i] ;Build(1 , n , 1) ;for(int i = 1 ; i <= n ; i ++) {if(fa[i] && !vis[fa[i]]) {Change(p[fa[i]] , n , size[fa[i]] - 1 , 1 , n , 1) ;vis[fa[i]] = 1 ;}int x = query(1 , n , size[i] , 1) ;x += cnt[x] ; p[i] = x ;Change(x , n , - size[i] , 1 , n , 1) ;}for(int i = 1 ; i <= n ; i ++) printf("%d ",d[p[i]]) ;return 0 ;
}
轉載于:https://www.cnblogs.com/beretty/p/9493594.html
與50位技術專家面對面20年技術見證，附贈技術全景圖
總結
以上是生活随笔為你收集整理的[九省联考2018]IIIDX的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
