遞增三元組

給定三個整數數組
A = [A1, A2, … AN],
B = [B1, B2, … BN],
C = [C1, C2, … CN]，
請你統計有多少個三元組(i, j, k) 滿足：

1 <= i, j, k <= N

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

【輸出格式】
一個整數表示答案

【樣例輸入】
3
1 1 1
2 2 2
3 3 3

【樣例輸出】
27

資源約定：
峰值內存消耗（含虛擬機） < 256M
CPU消耗 < 1000ms

請嚴格按要求輸出，不要畫蛇添足地打印類似：“請您輸入…” 的多余內容。

注意：
main函數需要返回0;
只使用ANSI C/ANSI C++ 標準;
不要調用依賴于編譯環境或操作系統的特殊函數。
所有依賴的函數必須明確地在源文件中 #include
不能通過工程設置而省略常用頭文件。

提交程序時，注意選擇所期望的語言類型和編譯器類型。

Ideas

首先我們要根據輸入數據的量級確定最終滿足要求的算法時間復雜度。

如果是用三層暴力循環求遞增三元組，那么算法的時間復雜度就是O(N ^ 3)，肯定不可能過所有的數據。

對于100%的數據，1 <= N <= 100000，所以最終滿足要求的算法時間復雜度應該是O(n * logn)的。

然后再來看題目要求，并沒有要求 i j k 的大小，所以我們可以先給三個數組進行升序排序。

然后對于B數組中的每一個數bi，我們可以在A數組中找到一個小于bi的最大數a，對應的索引為a_idx，同樣可以在C數組中找到一個大于bi的最小數b,對應的索引為b_idx。

根據a_idx和b_idx，我們可以求出對應A數組中小于bi的元素個數 num_1，也可以求出C數組中大于bi的元素個數 num_2，根據乘法原理，bi對應的符合條件的遞增三元組個數為 num_1 * num_2。

遍歷整個B數組，對于每個元素bi都在A、B數組中求出相應的 num_1 * num_2，最后累加在一起就可以了。

Code

Python

from bisect import bisect_left, bisect_rightif __name__ == '__main__':ans = 0n = int(input())A = sorted(list(map(int, input().split())))B = sorted(list(map(int, input().split())))C = sorted(list(map(int, input().split())))for item in B:num_1 = bisect_left(A, item)num_2 = n - bisect_right(C, item)print(num_1, num_2)ans += num_1 * num_2print(ans)

總結

以上是生活随笔為你收集整理的2018年第九届蓝桥杯 - 省赛 - C/C++大学B组 - F.递增三元组的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。