IIIDX[九省联考2018]

题目传送门

题目背景

Osu 听过没？那是Konano 最喜欢的一款音乐游戏，而他的梦想就是有一天自己也能做个独特酷炫的音乐游戏。现在，他在世界知名游戏公司KONMAI 内工作，离他的梦想也越来越近了。

这款音乐游戏内一般都包含了许多歌曲，歌曲越多，玩家越不易玩腻。同时，为了使玩家在游戏上~~氪更多的金钱~~花更多的时间，游戏一开始一般都不会将所有曲目公开，有些曲目你需要通关某首特定歌曲才会解锁，而且越晚解锁的曲目难度越高。

题目描述

这一天，Konano 接到了一个任务，他需要给正在制作中的游戏《IIIDX》安排曲目的解锁顺序。游戏内共有n 首曲目，每首曲目都会有一个难度d，游戏内第i 首曲目会在玩家Pass 第 $lfloor frac{i}{k} floor$

举个例子：当k = 2 时，第1 首曲目是无需解锁的（ $lfloor frac{1}{2} floor$

Konano 的工作，便是安排这些曲目的顺序，使得每次解锁出的曲子的难度不低于作为条件需要玩家通关的曲子的难度，即使得确定顺序后的曲目的难度对于每个i 满足

$d_i geq d_{lfloor frac{i}{k} floor}di≥d⌊ki⌋$

当然这难不倒曾经在信息学竞赛摸鱼许久的Konano。那假如是你，你会怎么解决这份任务呢？

输入输出格式

输入格式：

从文件iiidx.in 中读入数据。

第1 行1 个正整数n 和1 个小数k，n 表示曲目数量，k 其含义如题所示。

第2 行n 个用空格隔开的正整数d，表示这n 首曲目的难度。

输出格式：

输出到文件iiidx.out 中。

输出1 行n 个整数，按顺序输出安排完曲目顺序后第i 首曲目的难度。

若有多解，则输出d1 最大的；若仍有多解，则输出d2最大的，以此类推。

输入输出样例

输入样例#1：

4 2.0
114 514 1919 810

输出样例#1：

114 810 514 1919

说明

　　第一眼，只会暴力怎么破（哭

　　码码码，样例过了。

　　第二眼，好像可以看成一棵树，子节点都不比父亲节点小？然后怎么做...

　　好像可以贪心！
　　码码码...发现我的贪心是错误的（哇哇大哭

　　看一眼题解。

　　嗯...线段树+二分答案？好像可以。

　　码码码...

　　对拍一波，没问题！

　　交了一波，只有50分（哭得歇斯里地

　　嗯。。因为复杂度是两个log，后面几个点T了很正常，但为啥还会有WA的啊！！！

　　再看一眼题解。（想看题解戳这里）

　　重复emmmm....好像重复确实会有问题qwq（为啥对拍不出来啊aaaaa

　　认真看了题解思路，emmmm...妙啊！

　　码码码...

　　debug了一个错误，对拍了两分钟,稳了！

　　交上去，A了。几个大数据600多ms，有点危险qaq （果然是自带大常数啊...

正解：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 #define LL long long
 7 #define RI register int
 8 using namespace std;
 9 const int INF = 0x7ffffff ;
10 const int N = 500000 + 10 ;
11 
12 inline int read() {
13     int k = 0 , f = 1 ; char c = getchar() ;
14     for( ; !isdigit(c) ; c = getchar())
15       if(c == '-') f = -1 ;
16     for( ; isdigit(c) ; c = getchar())
17       k = k*10 + c-'0' ;
18     return k*f ;
19 }
20 
21 struct Node {
22     int mi, laz ;
23     Node *ls, *rs ;
24     inline void pushup() {
25         mi = min(ls->mi,rs->mi) ;
26     }
27     inline void pushdown(int l,int r) {
28         if(!laz) return ; int mid = (l+r)>>1 ;
29         ls->mi += laz, rs->mi += laz ;
30         ls->laz += laz, rs->laz += laz ;
31         laz = 0 ;
32     }
33 }pool[N<<1] ;
34 inline Node *newNode() {
35     static int cnt = 0 ;
36     return &pool[++cnt] ;
37 }
38 Node *build(int l,int r) {
39     Node *cur = newNode() ;
40     if(l == r) {
41         cur->mi = l ;
42     } else {
43         int mid = (l+r)>>1 ;
44         cur->ls = build(l,mid) ; cur->rs = build(mid+1,r) ;
45         cur->pushup() ;
46     }
47     return cur ;
48 }
49 void change_interval(Node *cur,int l,int r,int a,int b,int x) {
50     if(l >= a && r <= b) {
51         cur->mi += x, cur->laz += x ; return ;
52     }
53     cur->pushdown(l,r) ;
54     int mid = (l+r)>>1 ;
55     if(a <= mid) change_interval(cur->ls,l,mid,a,b,x) ;
56     if(b > mid) change_interval(cur->rs,mid+1,r,a,b,x) ;
57     cur->pushup() ;
58 }
59 int query(Node *cur,int l,int r,int k) {
60     if(l == r) {
61         return cur->mi >= k ? l : l+1 ;
62     }
63     cur->pushdown(l,r) ;
64     int mid = (l+r)>>1 ;
65     if(cur->rs->mi >= k) return query(cur->ls,l,mid,k) ;
66     else query(cur->rs,mid+1,r,k) ;
67 }
68 
69 int n ; double k ; int hh[N], fa[N], siz[N], ans[N], cnt[N] ;
70 
71 inline bool cmp1(int s,int t) { return s > t ; }
72 int main() {
73     n = read() ; scanf("%lf",&k) ;
74     for(int i=1;i<=n;i++) hh[i] = read() ;
75     sort(hh+1,hh+n+1,cmp1) ;
76     for(int i=1;i<=n;i++) fa[i] = floor(i/k), siz[i] = 1 ;
77     for(int i=n;i;i--) {
78         cnt[i] = hh[i] == hh[i+1] ? cnt[i+1]+1 : 0 ;
79         siz[fa[i]] += siz[i] ;
80     }
81     Node *root = build(1,n) ;
82     for(int i=1;i<=n;i++) {
83         if(fa[i] && fa[i] != fa[i-1]) change_interval(root,1,n,ans[fa[i]],n,siz[fa[i]]-1) ;
84         int x = query(root,1,n,siz[i]) ;
85         x += cnt[x], cnt[x]++, x -= (cnt[x]-1) ; ans[i] = x ;
86         change_interval(root,1,n,x,n,-siz[i]) ;
87     }
88     for(int i=1;i<=n;i++) printf("%d ",hh[ans[i]]) ;
89     return 0 ;
90 }

一开始竟然忘记pushdown了，好像没睡醒=-=

暴力：

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<bitset>
 6 #define LL long long
 7 #define RI register int
 8 using namespace std;
 9 const int INF = 0x7ffffff ;
10 const int N = 100 + 10 ;
11 
12 inline int read() {
13     int k = 0 , f = 1 ; char c = getchar() ;
14     for( ; !isdigit(c) ; c = getchar())
15       if(c == '-') f = -1 ;
16     for( ; isdigit(c) ; c = getchar())
17       k = k*10 + c-'0' ;
18     return k*f ;
19 }
20 int n ; double k ; int pre[N], d[N], res[N] ;
21 bitset<N>vis ; bool flag = 0 ;
22 
23 void dfs(int x) {
24     if(x == n+1) {
25         flag = 1 ; 
26         for(int i=1;i<=n;i++) printf("%d ",res[i]) ;
27         return ;
28     }
29     for(int i=1;i<=n;i++) {
30         if(flag) return ;
31         if(!vis[i] && d[i] >= res[pre[x]]) {
32             vis[i] = 1 ; res[x] = d[i] ;
33             dfs(x+1) ; vis[i] = 0 ;
34         }
35     }
36 }
37 
38 inline bool cmp1(int s,int t) { return s > t ; }
39 int main() {
40     n = read() ; scanf("%lf",&k) ;
41     for(int i=1;i<=n;i++) {
42         d[i] = read() ; pre[i] = (double)i/k ;
43     }
44     sort(d+1,d+n+1,cmp1) ;
45     dfs(1) ;
46     return 0 ;
47 }

二分答案+线段树：

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<vector>
  6 #define LL long long
  7 #define RI register int
  8 using namespace std;
  9 const int INF = 0x7ffffff ;
 10 const int N = 500000 + 10 ;
 11 
 12 inline int read() {
 13     int k = 0 , f = 1 ; char c = getchar() ;
 14     for( ; !isdigit(c) ; c = getchar())
 15       if(c == '-') f = -1 ;
 16     for( ; isdigit(c) ; c = getchar())
 17       k = k*10 + c-'0' ;
 18     return k*f ;
 19 }
 20 
 21 int n ; int d[N], siz[N] ; double k ; bool vis[N] ;
 22 vector<int>v[N] ;
 23 
 24 void dfs1(int x,int fa) {
 25     vis[x] = 1 ; int mm = v[x].size() ; siz[x] = 1 ;
 26     for(int i=0;i<mm;i++) {
 27         int y = v[x][i] ; if(vis[y]) continue ;
 28         dfs1(y,x) ; siz[x] += siz[y] ;
 29     }
 30 }
 31 
 32 struct Node {
 33     int val, laz ;
 34     Node *ls, *rs ;
 35     inline void pushup() {
 36         val = 0 ;
 37         if(ls) val += ls->val ;
 38         if(rs) val += rs->val ;
 39     }
 40     inline void pushdown(int l,int r) {
 41         if(!laz) return ;
 42         int mid = (l+r)>>1 ;
 43         ls->val += laz*(mid-l+1) ; rs->val += laz*(r-mid) ;
 44         ls->laz += laz, rs->laz += laz ;
 45         laz = 0 ;
 46     }
 47 }pool[N<<1] ; int a, b, x ;
 48 inline Node *newNode() {
 49     static int cnt = 0 ;
 50     return &pool[++cnt] ;
 51 }
 52 Node *build(int l,int r) {
 53     Node *cur = newNode() ;
 54     if(l == r) {
 55         cur->val = n-l ; 
 56     } else {
 57         int mid = (l+r)>>1 ;
 58         cur->ls = build(l,mid) ; cur->rs = build(mid+1,r) ;
 59         cur->pushup() ;
 60     }
 61     return cur ;
 62 }
 63 void change_interval(Node *cur,int l,int r) {
 64     if(l >= a && r <= b) {
 65         cur->laz += x, cur->val += x*(r-l+1) ; return ;
 66     }
 67     cur->pushdown(l,r) ; int mid = (l+r)>>1 ;
 68     if(a <= mid) change_interval(cur->ls,l,mid) ;
 69     if(b > mid) change_interval(cur->rs,mid+1,r) ;
 70     cur->pushup() ;
 71 }
 72 int ask_point(Node *cur,int l,int r) {
 73 //    printf("zzz
") ;
 74     if(l == r) return cur->val ;
 75     cur->pushdown(l,r) ; int mid = (l+r)>>1 ;
 76     if(x <= mid) return ask_point(cur->ls,l,mid) ;
 77     else return ask_point(cur->rs,mid+1,r) ;
 78 }
 79 
 80 Node *root ; int ans[N] ;
 81 inline bool check(int kk,int xx) {
 82     x = kk ;
 83     int res = ask_point(root,1,n) ; // printf("res:%d
",res) ;
 84     if(res >= siz[xx]-1) return 1 ;
 85 //    if(ask_point(root,1,n) >= siz[xx]-1) return 1 ;
 86     return 0 ;
 87 }
 88 
 89 bool vv[N] ;
 90 void dfs2(int xx,int fa) {
 91     vis[xx] = 1 ; 
 92     int L = 1, R = n, res = 0 ;
 93     while(L < R) {
 94         int mid = (L+R)>>1 ; while(vv[mid]) mid++ ; if(mid > R) { R = (L+R)>>1 ; continue ; }
 95         if(check(mid,xx)) res = max(res,mid), L = mid+1 ;
 96         else R = mid ;
 97     }
 98     if(!vv[R] && check(R,xx)) res = max(res,R) ;
 99     ans[xx] = d[res], vv[res] = 1 ; //  printf("%d:%d %d
",xx,res,ans[xx]) ;
100     a = 1, b = res-1, x = -1 ; if(b) change_interval(root,1,n) ; 
101     int mm = v[xx].size() ;
102     for(int i=0;i<mm;i++) {
103         int y = v[xx][i] ; if(y == fa) continue ;
104         dfs2(y,xx) ;
105     }
106 }
107 
108 int main() {
109     n = read() ; scanf("%lf",&k) ;
110     for(int i=1;i<=n;i++) {
111         d[i] = read() ; int x = (double)i/k ;
112         v[x].push_back(i) ;
113     }
114     sort(d+1,d+n+1) ;
115     for(int i=1;i<=n;i++) sort(v[i].begin(),v[i].end()) ;
116     for(int i=1;i<=n;i++) if(!vis[i]) dfs1(i,0) ;
117     memset(vis,0,sizeof(vis)) ; root = build(1,n) ;    
118     for(int i=1;i<=n;i++) if(!vis[i]) dfs2(i,0) ;
119     for(int i=1;i<=n;i++) printf("%d ",ans[i]) ;
120     return 0 ;    
121 }

// 注释掉的内容为用于调试的代码