蓝桥杯2018年第九届真题-递增三元组-二分查找时间复杂最短题解（Java代码）

解题思路:

利用排序加二分查找的算法，代码中的end是每次算完之后小于key的最大的数的下标，将a中小于b的数的数量算出来之后再进行累加，可以减少c对b中小于c的数的访问时需要从小于c的b中的各个数对应大于a的数的累加。从而缩短计算时间，这个算法的复杂度是O(nlogn)

注意事项:
我语言组织不是很好，所以希望读者代码自己敲一遍，就可以发现其中的奥妙，多调试。

参考代码:

package LanQiao.第九届2018;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main递增三元组 {
   /*
   1 2 3
   2 3 4
   3 4 5
   思想：
   二分查找
    */
   private static StreamTokenizer st =new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
   private static int n;

   public static void main(String[] args) throws IOException {
       double start = System.currentTimeMillis();
       st.nextToken();
       n=(int)st.nval;
       int[] a=new int[n];
       int[] b=new int[n];
       int[] c=new int[n];
       for(int i=0;i<n;i++){
           st.nextToken();
           a[i]=(int)st.nval;
       }
       for(int i=0;i<n;i++){
           st.nextToken();
           b[i]=(int)st.nval;
       }
       for(int i=0;i<n;i++){
           st.nextToken();
           c[i]=(int)st.nval;
       }
       Arrays.sort(a);
       Arrays.sort(b);
       Arrays.sort(c);
       int ltb[]=new int[n];
       for(int i=0;i<n;i++){
           int key=b[i];
           int begin=0,end=n-1;
           while(begin<=end){
               int mid=(begin+end)/2;
               if(a[mid]<key){
                   begin=mid+1;
               }
               else{
                   end=mid-1;
               }
           }
           if(i==0)ltb[i]=end+1;
           else ltb[i]=ltb[i-1]+end+1;
       }
       long ans=0;
       for(int i=0;i<n;i++){
           int key=c[i];
           int begin=0,end=n-1;
           while(begin<=end){
               int mid=(begin+end)/2;
               if(b[mid]<key){
                   begin=mid+1;
               }
               else{
                   end=mid-1;
               }
           }
           if(end!=-1)ans+=ltb[end];
       }
       System.out.println(ans);
       System.out.println(System.currentTimeMillis()-start+"ms");
   }
}