CF1676H1 Maximum Crossings (Easy Version) 题解

5k_sync_closer · 2022-05-11 16:02:55 · 题解

题意

一个终端是一排 n 个连接在一起的相等的线段，有两个终端，一上一下。

有一个数组 a_i，代表从上面的终端中第 i 条线段，到下面的终端中第 a_i 条线段，有一条连线。

问这些连线最多有几个交点。

思路

考虑何时两条连线会有交点。

观察样例不难得到，若 i<j 且 a_i≥a_j，则两条连线有交点。

直接枚举每一对 i,j 即可，复杂度 O(n^2)。

另外，这是一个二维偏序问题，可以 O(n\log n) 完成。

代码

#include <cstdio>
int T, n, s, a[1050];
int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);s = 0;
        for(int i = 1;i <= n;++i)
            scanf("%d", &a[i]);
        for(int i = 1;i <= n;++i)
            for(int j = i + 1;j <= n;++j)
                s += a[i] >= a[j];
        printf("%d\n", s);
    }
    return 0;
}