import java.util.Scanner; 
class Special_Pairs{ 

private static Scanner scan; 


public static void main(String [] args) { 
    byte t; 
    int n; 
    scan = new Scanner(System.in); 
    t=scan.nextByte(); 
    int[] a=new int[100000]; 
    while(t>0) 
    { 
     int i,j,count=0; 
     n=scan.nextInt(); 
    for(i=0;i<n;i++) 
    { 
     a[i]=scan.nextInt(); 
    } 
    for(i=0;i<n;i++) 
    { 
     for(j=0;j<n;j++) 
     { 
      if(((a[i]&a[j])==0)||((a[j]&a[i])==0)) 
      { 
       count++; 
      } 
     } 
    } 
    t--; 
    System.out.println(count); 
    }  
} 
}

幫助我減少時間這個程序的複雜性大大縮短開發週期以下程序的複雜性

問：

您已經給出了關於大小N的整數數組A你必須報告的數量有序配對(i,j)，例如A[i] & A[j]=0。這裏&表示BITWISE AND(i,j)和(j,i)被認爲是不同的。

輸入：第一行包含T個測試用例。每個測試的第一行包含N.下一行包含N個整數 - 第i個整數A [i]。

輸出：輸出每個測試用例的這種對數。

限制條件：T≤10; N≤100000; A [1]≤百萬

採樣輸入（明文鏈路）

1 5 41 47 34 40 29

樣本輸出（明文鏈路）

2

說明：這些是需要對(3 5)(5 3)

來源

2015-09-04 Mohamed Nadeem

歡迎StackOverflow上，這不是一個代碼編寫/功課解決服務，表現出一定的努力。你試過什麼了？ – yvesmancera

我會爲此建議三個優化。我也修改了代碼。

對於外循環的每次迭代，您無需始終從0開始。第二個循環可以從第一個循環的current+1開始。所以不會比較你已經比較過的元素。
您不需要檢查對(i,j)和(j,i)。如果一個是零，那麼其他將始終爲零。
您不需要使用修訂大小來初始化陣列。您始終可以將其初始化爲n的值。

import java.util.Scanner; 

public class Pairs { 
    public static void main(String [] args) { 
    Scanner scan = new Scanner(System.in); 
    int t = scan.nextInt(); 
    while(t > 0) { 
     t--; 
     int count = 0; 
     int n = scan.nextInt(); 
     int a[] = new int[n]; 
     for(int i = 0; i<n; i++) { 
     a[i]=scan.nextInt(); 
     } 
     for(int i = 0; i<n-1; i++) { 
     for(int j = i+1; j<n; j++) { 
      if((a[i] & a[j])==0) 
      { 
      count += 2; 
      } 
     } 
     } 
     System.out.println(count); 
    } 
    } 
}

來源

2015-09-04 19:44:49 YoungHobbit

2.你不需要同時測試'（a [i]＆a [j]）== 0'和'（a [j]＆a [i]）== 0'。只有一個就足夠了。（哦，老兄，你編輯的速度比我輸入的速度還快。呵呵） – Paulo

感謝您的幫助...... @ Abhishek Bafna –

如果您參加編程競賽（如ICPC或類似的活動），也許您不應該使用Scanner。從鍵盤讀取速度太慢。我已經參加過ICPC比賽了，但我曾經使用過C++。也許你應該試試BufferedReader而不是Scanner。

來源

2015-09-04 19:44:37 Paulo

大大縮短開發週期以下程序的複雜性

問：

回答

相關問題