[蓝桥杯2018年第九届真题-递增三元组] 排序 + 暴力枚举解法 和 双指针解法

解题思路: 1.先排序，再枚举每种情况就行
                2.对于双指针，因为题目是要Ai < Bj < Ck, 所以只要找到A小于B的个数和C大于B的个数，用乘法原理得出答案。
参考代码:

(暴力)

#include

using namespace std;

const int N = 100010;

int a[N], b[N], c[N];

typedef long long ll;

int main(void) {

    ll ans = 0;

    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    for (int i = 0; i < n; i++) scanf("%d", &b[i]);

    for (int i = 0; i < n; i++) scanf("%d", &c[i]);

    sort(a, a + n);

    sort(b, b + n);

    sort(c, c + n);

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

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

            if (b[j] > a[i]) {

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

                    if (c[k] > b[j]) {

                        ans += (n - k);

                        break;

                    }

                }

            }

        }

    }

    printf("%lld\n", ans);

    return 0;

}

(双指针)

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int a[N], b[N], c[N];

typedef long long ll;

int main(void) {

    ll ans = 0;

    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; i++) scanf("%d", &a[i]);

    for (int i = 0; i < n; i++) scanf("%d", &b[i]);

    for (int i = 0; i < n; i++) scanf("%d", &c[i]);

    sort(a, a + n);

    sort(b, b + n);

    sort(c, c + n);

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

        while (j < n && a[j] < b[i]) j++;

        while (k < n && c[k] <= b[i]) k++;

        ans += (ll)j * (n - k);

    }

    printf("%lld\n", ans);

    return 0;

}