蓝桥杯2018年第九届真题-递增三元组(很简洁易懂)

解题思路:

注意事项:

参考代码:

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5 + 7;

int a[N];

int b[N];

int c[N];

int n;

int main()

{

    cin >> n;

    for (int i = 0; i < n; i++) {

        cin >> a[i];

    }

    for (int i = 0; i < n; i++) {

        cin >> b[i];

    }

    for (int i = 0; i < n; i++) {

        cin >> c[i];

    }

    int res = 0;

    sort(a, a + n);

    sort(b, b + n);

    sort(c, c + n);

    int p = 0;

    int q = 0;

    for (int i = 0; i < n; i++) {

        int v = b[i];

        while (p < n && a[p] < v) {

            p++;

        }

        while (q < n && c[q] <= v) {

            q++;

        }

        res += p * (n - q);

    }

    cout << res << endl;

    return 0;

}