給定一個長度為N的數組A=[A₁, A₂, ... A_N]，已知其中每個元素A_i的值都只可能是1, 2或者3。

請求出有多少下標三元組(i, j, k)滿足1 ≤ i < j < k ≤ N且A_i < A_j < A_k。

Input

第一行包含一個整數N ?

第二行包含N個整數A₁, A₂, ... A_N。(1 ≤ A_i ≤ 3) ?

對于30%的數據，1 ≤ N ≤ 100 ?

對于80%的數據，1 ≤ N ≤ 1000 ?

對于100%的數據，1 ≤ N ≤ 100000 ?

Output

一個整數表示答案

Sample Input

6 1 3 2 1 2 3

Sample Output

3
代碼： #include<stdio.h> #define MAX 100005 long long int n; long long int digit[MAX],a,c; long long int sum=0; int main() {int i;scanf("%d",&n);for(i=1;i<=n;i++){scanf("%d",&digit[i]);if(digit[i]==3)c++;}for(i=1;i<=n;i++){if(digit[i]==1)a++;if(digit[i]==3)c--;if(digit[i]==2)sum+=a*c;}printf("%lld\n",sum);return 0; }

　　思路：

比如 10 1? 2 3 1 2 3 1 2 3 3? ==16

3有四個? 然后剛開始找到第一個2時???ans=ans+1*4? 之后4--===3了? 然后i=2? 之后找到第二個2此刻利用這個2得是2*3==6+4==10

然后3有兩個了 之后1有三個了 然后利用第三個2得有3*2==6 ?

轉載來自http://blog.csdn.net/islittlehappy/article/details/77963099

?

自己寫的怎么改都沒通過，最后copy了下大佬的代碼過掉了，我的答案都是對的，估計是哪里的格式沒有注意到，小問題。刷題傷腦子。。。

轉載于:https://www.cnblogs.com/zw431387/p/10254749.html

總結

以上是生活随笔為你收集整理的指针A - 签到题（顺序三元组）的全部內容，希望文章能夠幫你解決所遇到的問題。

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