当前位置：网站首页>【7.8】Educational Codeforces Round 131 (Rated for Div. 2)

【7.8】Educational Codeforces Round 131 (Rated for Div. 2)

2022-07-19 13:40:00 【ZhgDgE】

ALL：6
AC：3
Supplementary questions ：1

D. Permutation Restoration

The question ： Here is a length of n ( n ≤ 2 × 1 0 5 ) n(n\leq 2\times 10^5) n(n≤2×105) Array a a a , b i = ⌊ i a i ⌋ b_i=\left\lfloor \frac{i}{a_i} \right\rfloor bi​=⌊ai​i​⌋ .

Now give b b b , Let you restore a a a . Make sure there's a solution .

Answer key ：Educational Codeforces Round 131 D( greedy )

Ideas ： First push the formula ： From the title, we can see b i = ⌊ i a i ⌋ b_i=\left\lfloor \frac{i}{a_i} \right\rfloor bi​=⌊ai​i​⌋ , namely b i ≤ i a i < b i + 1 b_i\leq \frac{i}{a_i}<b_i+1 bi​≤ai​i​<bi​+1 , namely i b i + 1 < a i ≤ i b i \frac{i}{b_i+1}<a_i\leq \frac{i}{b_i} bi​+1i​<ai​≤bi​i​ , namely a i ∈ [ ⌊ i b i + 1 ⌋ + 1 , ⌊ i b i ⌋ ] a_i\in [\left\lfloor\frac{i}{b_i+1}\right\rfloor+1, \left\lfloor\frac{i}{b_i}\right\rfloor] ai​∈[⌊bi​+1i​⌋+1,⌊bi​i​⌋] .

The problem turns into a known L i , R i , i ∈ [ 1 , n ] L_i,R_i,i\in[1,n] Li​,Ri​,i∈[1,n] , Please arrange a i ∈ [ 1 , n ] a_i\in[1,n] ai​∈[1,n] Satisfy L i ≤ a i ≤ R i L_i\leq a_i\leq R_i Li​≤ai​≤Ri​ , Similar to a task scheduling problem . Because the arrangement elements are different , We can enumerate 1 ∼ n 1\sim n 1∼n To allocate . Every time you enumerate to i i i Find out all L j ≤ i L_j\leq i Lj​≤i The range of , And find the leftmost assignment of the right endpoint in these intervals .

AC Code ：https://codeforces.com/contest/1701/submission/163997864

原网站

版权声明
本文为[ZhgDgE]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/200/202207171827573902.html

边栏推荐

猜你喜欢

随机推荐