提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  .Net

当前栏目

顺序三元组

2023-02-18 16:35:27 时间

顺序三元组

给定一个长度为 N 的数组 A=[A_1, A_2, ... A_N]，已知其中每个元素 Ai​ 的值都只可能是 1, 2 或者 3。

请求出有多少下标三元组 (i, j, k)满足 1≤i<j<k≤N 且 Ai​<Aj​<Ak​。

输入格式

第一行包含一个整数 N;

第二行包含 N 个整数A1​,A2​,...AN​。(1≤Ai​≤3,1≤N≤100000)。

输出格式

一个整数表示答案。

输出时每行末尾的多余空格，不影响答案正确性

样例输入

6
1 3 2 1 2 3

样例输出

3

代码：

1）未优化前的代码：暴力破解

思路：从第一个数A1之后找第二个大于A1的数A2，再在A2之后找一个大于A2的数

 #include<iostream>
 using namespace std;
int main(){
     int n;
     cin>>n;
     int *arr=new int[n];
     for (size_t i = 0; i < n; i++)
     {
         cin>>arr[i];
      }
     int count=0;
     for (int i = 0; i < n-2; i++)
     {
         for (int j = i+1; j <n-1 ; j++)
         {
             for (int k = j+1; k <n ; k++)
             {
                 if (arr[i]<arr[j]&&arr[j]<arr[k])
                 {
                     count++;
                 }
             }
         }
     }
     cout<<count<<endl;
 }

 2）优化后：

 #include <iostream>
 using namespace std;
 int main(){
     long long N;
     cin>>N;
     int *in = new int[N+1];
      long long a=0,b=0,c=0;
     // a是记录1的个数，c是记录3的个数
     for(long long i=0;i<N;i++)
      {
         cin>>in[i];
         if(in[i]==3)c++;
     }
     long long ans=0;
     for(long long i=0;i<N;i++)
     {
         if(in[i]==1)a++;    
         if(in[i]==3)c--;
         if(in[i]==2){
     //以2为中间点，由2之前1的个数与2之后3的个数计算递增三元组组合
             ans+=a*c;
         }
     }
     cout<<ans<<endl;
 }

相关文章