ID: 557

Difficulty: 4

所属公司 : 阿里

时间 :2023年9月3日-阿里云

题目描述

小红有 $n$ 个点，第 $i$ 个点的权值为 $w_i$ 。

思路：思维

首先，一种极端情况是所有的点的权值都相同，那么此时每个点只能连一条边。答案为 $\lfloor\frac{n}{2}\rfloor$ 。

接下来，对于普通的情况，由于不允许出现 $w_x\leq w_y\leq w_z$ 的这样三个点有 $x$ 连 $y$ ， $y$ 连 $z$ 的情况。

所以考虑将这些数排序，然后分成两部分。

两部分数有绝对的大小关系。