2020-10-04

    科技2022-07-17  99

    题目: 给定三个整数数组 A = [A1, A2, … AN], B = [B1, B2, … BN], C = [C1, C2, … CN], 请你统计有多少个三元组(i, j, k) 满足: 1. 1 <= i, j, k <= N 2. Ai < Bj < Ck 【输入格式】  第一行包含一个整数N。 第二行包含N个整数A1, A2, ... AN。 第三行包含N个整数B1, B2, ... BN。 第四行包含N个整数C1, C2, ... CN。

    对于30%的数据,1 <= N <= 100   对于60%的数据,1 <= N <= 1000  对于100%的数据,1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000 

    【输出格式】 一个整数表示答案 解题思路: 关键是数组b,从头开始遍历,在a数组中找到比b[j]小的元素个数(x),在c组中找到比b[j]大的元素个数(y), 所以 a[i] < b[j] < c[k]的元组个数就为 x * y;

    代码:

    #include <iostream> #include <algorithm>  using namespace std; int main() {     int n;     cin >> n;     int *a = new int[n];     int *b = new int[n];     int *c = new int[n];     int i;     //输入      for (i = 0; i < n; i++)         cin >> a[i];     for (i = 0; i < n; i++)         cin >> b[i];     for (i = 0; i < n; i++)         cin >> c[i];          sort(a, a + n);//默认是从小到大     sort(b, b + n);     sort(c, c + n);      int sum = 0;     for (i = 0; i < n; i++)     {         int x = lower_bound(a, a + n, b[i]) - a;         /*lower_bound()函数头文件:algorithm,意思是在a[0]到a[n - 1]中找到比b[i]小的元素地址,减去         数组的初始位置a后,就得到比b[i]小的首个元素下标,而数组下标是从0开始的,所以x就是a中比b[i]         小的元素个数*/         int y = n - (upper_bound(c, c + n, b[i]) - c);         sum += x * y;     }      cout << sum << endl;     return 0; }

    Processed: 0.009, SQL: 8