HBC247405货币系统,贪心惊鹊题解

凯凯我们等你回来算法基础篇 2023-11-24 06:05:02 55 0

挑战自我，勇攀编程高峰！全网最全C++题库，助您成为编程达人。

P的前缀最小值变化次数（即满足如下条件的。forall 1le j < i , P_{j} > P_{i}. P，请构造一个排列

对于长度为 n n的排列 P P，定义 f(P) f(P)为 P P的前缀最小值变化次数（即满足如下条件的 i i的个数： 1le i le n 1≤i≤n且 forall 1le j < i , P_{j} > P_{i} ∀1≤jP i ）。现在给定排列 P P，请构造一个排列 Q Q，使得 max(f(Q),f(Q')) max(f(Q),f(Q ′ ))尽量小。其中 Q' = Q_{P_{1}},Q_{P_{2}}...Q_{P_{n}} Q ′ =Q P 1 ,Q P 2 ...Q P n 。