~~~題面~~~

題解：

　　一開始翻網(wǎng)上題解看了好久都沒看懂，感覺很多人都講得不太詳細(xì)，所以導(dǎo)致一些細(xì)節(jié)的地方看不懂，所以這里就寫詳細(xì)一點(diǎn)吧，如果有不對(duì)的or不懂的可以發(fā)評(píng)論在下面。

　　首先有一個(gè)比較明顯的50分貪心：

　　先把d排好序，然后按從小到大的順序貪心的給每個(gè)點(diǎn)選值，同等條件下優(yōu)先編號(hào)大的，于是越小的值會(huì)越趨近于放在編號(hào)越大的上面。

　　但是這樣在數(shù)字重復(fù)的情況下是不對(duì)的，?比如下面這組數(shù)據(jù)：

　　4 3.0

　　1 1 2 2

　　貪心會(huì)得到1 1 2 2 ,而正確答案是1 2 2 1.

　　因此換個(gè)角度考慮，在什么情況下一個(gè)點(diǎn)可以取到一個(gè)值x？

　　設(shè)這個(gè)點(diǎn)的子樹大小為Size[i],那么這個(gè)點(diǎn)可以取到值x，當(dāng)且僅當(dāng)大于等于x的還沒被取的值的個(gè)數(shù) >= Size[i]，原因應(yīng)該是很好理解的，畢竟還要有Size[i] - 1和比x大的值放在i的子樹上才行。

　　因此我們先對(duì)d從小到大排序去重，統(tǒng)計(jì)每個(gè)值的出現(xiàn)次數(shù)cnt[x],?然后對(duì)于每個(gè)數(shù)統(tǒng)計(jì)一個(gè)f[x]表示大于等于x的還沒被取的值的個(gè)數(shù)為f[x].

　　

　　假設(shè)我們給節(jié)點(diǎn)i匹配上了一個(gè)值x，那么這個(gè)策決策對(duì)小于等于x的值的影響是確定的，因此將所有小于等于x的值的f數(shù)組都減小SIze[i],表示這些值的右邊可以取的值又減小了Size[i]個(gè)。

　　我們將和這個(gè)操作稱為“預(yù)定”，因?yàn)槲覀儸F(xiàn)在并不知道點(diǎn)i的子樹分別會(huì)選擇哪些值，但我們知道它們要選幾個(gè)值，所以我們相當(dāng)于先告訴后面的人，這個(gè)節(jié)點(diǎn)i已經(jīng)坐到了x這個(gè)值上，并且要求后面的人為它的子樹留Size[i] - 1個(gè)座位。

　　因?yàn)檫@個(gè)決策對(duì)大于x的值的影響是不確定的，我們暫時(shí)沒有修改它，但其實(shí)這個(gè)決策會(huì)對(duì)它產(chǎn)生影響，那么對(duì)于一個(gè)值k，在取它之前的決策到底對(duì)它產(chǎn)生了什么樣的影響呢？

　　對(duì)于一個(gè)值k，它的真正的f[k]其實(shí)是min(f[1], f[2], f[3] ....f[k]),因?yàn)槊總€(gè)f值都相當(dāng)于一個(gè)后綴和，一個(gè)合法的值不能使得f[k]反而比它前面的f值更大，因?yàn)榍懊娴膄值要比f[k]統(tǒng)計(jì)了更多的數(shù)。

　　

　　因?yàn)轭}目要求使得字典序最大，所以我們按照編號(hào)從小到大給節(jié)點(diǎn)分配值顯然是最優(yōu)的。

　　因此我們每次就是要在剩下的數(shù)上尋找一個(gè)最靠右的，并且使得min(f[1], f[2], f[3] ...f[k]) >= Size[i]的k。

　　因?yàn)樯婕皡^(qū)間修改和查詢，我們使用線段樹來維護(hù)所有的f值，每次選好一個(gè)值，我們就把一些已經(jīng)確定的影響從線段樹中刪除（對(duì)一個(gè)區(qū)間進(jìn)行- Size[i]的操作）。

　　對(duì)于每次選值，我們都可以在線段樹上進(jìn)行二分來查找滿足上述粗體字要求的最靠右的值。

　　值得注意的是，在每次查詢前，如果一個(gè)節(jié)點(diǎn)的父親的影響還沒有被撤銷的話，應(yīng)該要撤銷它父親的影響。（即把父親給子樹占的座給加回來 ：1 ~ 父親匹配值的f值 加上 Size[fa] - 1）

　　為什么呢？

　　想象一下，如果不撤銷父親的影響的話，豈不是相當(dāng)于別人特意給你占了座，結(jié)果你自己還不能坐上去？

　　因?yàn)橐粋€(gè)節(jié)點(diǎn)的兒子都是連續(xù)的，所以我們?cè)诔蜂N的父親的影響后，會(huì)馬上把不應(yīng)該撤銷的部分給補(bǔ)上（兒子的子樹在不斷的加上來），所以不用擔(dān)心對(duì)之后的決策造成影響。

　　

1 #include<bits/stdc++.h> 2 using namespace std; 3 #define R register int 4 #define AC 551000 5 #define ac 2500000 6 7 int n, w, go, tot, rnt; 8 double k; 9 int ans[AC], cnt[AC], father[AC], Size[AC], f[AC], s[AC];//cnt[i]表示排名第i位的d值出現(xiàn)的次數(shù) 10 bool done[AC]; 11 12 inline int read() 13 { 14 int x = 0;char c = getchar(); 15 while(c > '9' || c < '0') c = getchar(); 16 while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); 17 return x; 18 } 19 20 inline int Min(int a, int b){ 21 return a > b ? b : a; 22 } 23 24 struct seg_tree{ 25 int tree[ac], lazy[ac], l[ac], r[ac]; 26 27 inline void update(int x){ 28 tree[x] = Min(tree[x * 2], tree[x * 2 + 1]); 29 } 30 31 inline void pushdown(int x) 32 { 33 if(lazy[x]) 34 { 35 int ll = x * 2, rr = ll + 1; 36 tree[ll] += lazy[x], tree[rr] += lazy[x]; 37 lazy[ll] += lazy[x], lazy[rr] += lazy[x]; 38 lazy[x] = 0; 39 } 40 } 41 42 void build(int x, int ll, int rr) 43 { 44 l[x] = ll, r[x] = rr; 45 if(ll == rr){tree[x] = f[ll]; return ;} 46 int mid = (ll + rr) >> 1; 47 build(x * 2, ll, mid), build(x * 2 + 1, mid + 1, rr); 48 update(x); 49 } 50 51 void change(int x, int ll, int rr) 52 { 53 pushdown(x); 54 if(l[x] == ll && r[x] == rr) 55 { 56 tree[x] += w, lazy[x] += w; 57 return ; 58 } 59 int mid = (l[x] + r[x]) >> 1; 60 if(rr <= mid) change(x * 2, ll, rr); 61 else if(ll > mid) change(x * 2 + 1, ll, rr); 62 else change(x * 2, ll, mid), change(x * 2 + 1, mid + 1, rr); 63 update(x); 64 } 65 66 void find(int x) 67 { 68 pushdown(x); 69 if(l[x] == r[x]){go = tree[x] >= w ? l[x] : l[x] - 1; return ;} 70 if(tree[x * 2] >= w) find(x * 2 + 1); 71 else find(x * 2); 72 update(x); 73 } 74 }T; 75 76 void pre() 77 { 78 n = read(), scanf("%lf", &k); 79 for(R i = 1; i <= n; i ++) s[i] = read(), Size[i] = 1; 80 sort(s + 1, s + n + 1); 81 for(R i = 1; i <= n; i ++) 82 { 83 ++ cnt[tot + 1]; 84 if(s[i] != s[i + 1]) s[++tot] = s[i]; 85 } 86 for(R i = tot; i; i --) 87 f[i] = f[i + 1] + cnt[i];//存下每個(gè)值右邊有多少個(gè)可供選擇的值 88 for(R i = n; i; i --) 89 father[i] = floor(i / k), Size[father[i]] += Size[i];//獲取每個(gè)節(jié)點(diǎn)的Size 90 T.build(1, 1, tot); 91 } 92 93 void work() 94 { 95 for(R i = 1; i <= n; i ++) 96 { 97 int fa = floor(i / k); 98 if(fa && !done[fa]) w = Size[fa] - 1, T.change(1, 1, ans[fa]);//如果有父親的話，要先把給兒子預(yù)定的節(jié)點(diǎn)還回來以幫助正確判斷 99 w = Size[i], done[fa] = true; 100 T.find(1), w = -Size[i];//先找到一個(gè)合法的點(diǎn) 101 T.change(1, 1, go);//再減去已經(jīng)被預(yù)定的位置 102 ans[i] = go; 103 printf("%d ", s[go]); 104 } 105 printf("\n"); 106 } 107 108 int main() 109 { 110 // freopen("in.in", "r", stdin); 111 pre(); 112 work(); 113 // fclose(stdin); 114 return 0; 115 } View Code

?

　　

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

總結(jié)

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

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