递增三元组（蓝桥杯18F）

暴力求解：

#include<iostream>
using namespace std;
int main() {int N;cin >> N;int* A = new int[N];int* B = new int[N];int* C = new int[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 cnt = 0;for (int i = 0; i < N;i++) {for (int j = 0; j < N; j++) {for (int z = 0; z < N; z++) {if (A[i]<B[j]<C[z]) {cnt++;}}}}cout << cnt;return 0;
}

优化排序加二分查找：

#include<iostream>
using namespace std;
void Qsort(int arr[], int L, int R) {if (L >= R) {return;}int left = L, right = R, key = arr[L], flag = 0;while (left < right) {if (flag == 0) {if (arr[right] < key) {arr[left] = arr[right];left++;flag = 1;}else {right--;}}else if (flag == 1) {if (arr[left] > key) {arr[right] = arr[left];right--;flag = 0;}else {left++;}}}arr[left] = key;Qsort(arr, L, left - 1);Qsort(arr, left + 1, R);
}
int tSearch_min(int* arr,int left,int right,int key, int tag) {if (tag == 0 && left>right) {return left;}else if(tag == 1 && left>right) {return left;}int mid = (left + right) / 2;if (key < arr[mid]) {return tSearch_min(arr, left, mid - 1, key, 0);}else if (key>arr[mid]) {return tSearch_min(arr, mid + 1, right, key, 1);}else {int i;for (i = mid; i >= left;i--) {if (arr[i] < key ) {return (i + 1);}}return (i + 1);}
}
int tSearch_max(int* arr, int left, int right, int key, int tag) {if (tag == 0 && left > right) {return left;}else if (tag == 1 && left > right) {return left;}int mid = (left + right) / 2;if (key < arr[mid]) {return tSearch_max(arr, left, mid - 1, key, 0);}else if (key > arr[mid]) {return tSearch_max(arr, mid + 1, right, key, 1);}else {int i;for (i = mid; i <= right; i++) {if (arr[i] > key) {return i;}}return i;}
}
int main() {int N;cin >> N;int* A = new int[N];int* B = new int[N];int* C = new int[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];}Qsort(A, 0, N - 1);Qsort(B, 0, N - 1);Qsort(C, 0, N - 1);int cnt = 0;for (int i = 0; i < N;i++) {int key = B[i];int min = tSearch_min(A, 0, N - 1, key, 0);int max = N - tSearch_max(C, 0, N - 1, key, 0);cnt += (min*max);}cout << cnt;return 0;
}