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

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

2022-07-17 18:28:00 【ZhgDgE】

ALL：6
AC：3
补题：1

D. Permutation Restoration

题意：这里有一个长度为 n ( n ≤ 2 × 1 0 5 ) n(n\leq 2\times 10^5) n(n≤2×105) 数组 a a a ， b i = ⌊ i a i ⌋ b_i=\left\lfloor \frac{i}{a_i} \right\rfloor bi​=⌊ai​i​⌋ 。

现在给出 b b b ，让你还原出 a a a 。保证一定有解。

题解：Educational Codeforces Round 131 D(贪心)

思路：先推一下公式：由题可知 b i = ⌊ i a i ⌋ b_i=\left\lfloor \frac{i}{a_i} \right\rfloor bi​=⌊ai​i​⌋ ，即 b i ≤ i a i < b i + 1 b_i\leq \frac{i}{a_i}<b_i+1 bi​≤ai​i​<bi​+1 ，即 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​ ，即 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​⌋] 。

问题转化为已知 L i , R i , i ∈ [ 1 , n ] L_i,R_i,i\in[1,n] Li​,Ri​,i∈[1,n] ，求排列 a i ∈ [ 1 , n ] a_i\in[1,n] ai​∈[1,n] 满足 L i ≤ a i ≤ R i L_i\leq a_i\leq R_i Li​≤ai​≤Ri​ ，类似于一个任务调度问题。因为排列元素不相同，我们可以枚举 1 ∼ n 1\sim n 1∼n 来分配。每次枚举到 i i i 时找出所有 L j ≤ i L_j\leq i Lj​≤i 的区间，并且在这些区间中找到右端点最靠左的分配。

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

原网站

版权声明
本文为[ZhgDgE]所创，转载请带上原文链接，感谢
https://blog.csdn.net/weixin_51948235/article/details/125765223

边栏推荐

猜你喜欢

随机推荐