思路：思维

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

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

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

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

两部分的大小分别为 $cnt_a$ ，$cnt_b$ ，满足集合 $a$ 中的数都小于集合 $b$ 的数。

那么答案为 $cnt_a\times cnt_b$

时间复杂度：$O(n\log n)$

cpp

#include <bits/stdc++.h>
using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    sort(a.begin(), a.end());
    
    long long ans = n / 2;
    for (int i = 0; i < n; ++i) {
        int j = i + 1;
        while (j < n && a[j] == a[i]) j += 1;
        // [0~j-1] 和 [j~n-1]
        ans = max(ans, 1ll * j * (n - j));
        i = j - 1;
    }
    
    cout << ans << "\n";

    return 0;
}

java

import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    static int N = 100000;
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            map.put(x, map.getOrDefault(x, 0) + 1);
        }
        long ans = 0;
        long cur = 0;
        for (Integer value : map.values()) {
            cur += value;
            ans = Math.max(ans, (cur) * (n - cur));
        }
        if (map.size() == 1) {
            System.out.println(n / 2);
        } else {
            System.out.println(ans);
        }
    }
}

python

n = int(input())
w = list(map(int, input().split()))
w.sort()

tmp = w[(n-1)//2]
a = n
b = 0
for i in range(n):
    if w[i] == tmp:
        a = min(a, i)
        b = max(b, i+1)
if a==0 and b==n:
    print(n//2)
else:
    print(max(a*(n-a), b*(n-b)))

题目描述

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

现在，小红想要用这 $n$ 个点建图。

但是建好的图要满足如果存在三个点 $a,b,c$ ，有边 a-b 和边 b-c ，那么不能有 $w_a\leq w_b\leq w_c$ 。

现在，小红想问你，建好的图上最多可以有多少条边。

输入描述

第一行，一个整数 $n(2 \leq n \leq 10^5)$，表示点数。
第二行，$n$ 个整数表示每个点的权值，第 $i$ 个数为 $w_i(1 \leq w_i \leq 10^5)$

输出描述

一个整数，表示建好的图上最多可以有多少条边。

样例

输入

4
1 2 3 4

输出

4

说明

可以连 1-3, 2-3, 1-4 和 2-4 这四条边。