WA in IITKWPCO SPOJ

Question

這是一個來自SPOJ的問題

小費魯達喜歡玩很多。如你所知，他只是玩數字。所以他給了n個數字。現在嘗試將數字分組爲不相交的集合，每個集合包含兩個數字。如果集合中的小數字恰好是大數的一半，他可以形成包含兩個數字的集合。

給定n個數字，找出他可以形成多少個最大數量的集合？

輸入

T：測試用例的數量。 （1 < = T < = 100）。

對於每個測試例：

第一行包含n個：（1 < = N < = 100）

然後下一行包含n個單個空間分隔。每個數字的範圍將介於1和10^6之間。

輸出

對於每個測試用例，輸出可以形成的最大數量的集合。

例

輸入：

輸出：

我的代碼::

#include <stdio.h> 
#include <math.h> 
#include <string.h> 

int main() 
{ 
    int t; 
    scanf("%d", &t); 

    while (t--) { 
      int n, i, j; 
      scanf("%d", &n); 
      long int arr[n], mini, maxi; 
      char str[105]; 

      for (i = 0;i < n;i++) { 
        str[i] = '0'; 
        scanf("%ld", &arr[i]); 
      } 

      for (i = 0;i < n;i++) { 
        for (j = 0;j < n;j++) { 
          mini = fmin(arr[i], arr[j]); 
          maxi = fmax(arr[i], arr[j]); 
          if ((maxi == 2 * mini) && (str[i] == '0' && str[j] == '0')) { 
            str[i] = str[j] = '1'; 
            break; 
          } 
        } 
      } 

      long int cnt = 0; 
      for (i = 0;i < n;i++) { 
        if (str[i] == '1') { 
          cnt++; 
        } 
      } 

      printf("%ld\n", cnt/2); 

    } 
    return 0; 
} 

有人可以PLZ指出我要去的地方錯誤或任何角落的測試情況下我是失蹤？？

Answer 1

你的邏輯存在缺陷。

考慮其中輸入數組是的情況下{2,4,1,8}

此答案應該是2中，由於集合可以形成{1,2}和{4,8} 。但是，對於這種情況，您的代碼將輸出1（它將將2與4配對，並且只能創建一個集合）。

我已經通過對數組進行排序來解決了這個問題，然後對每個元素檢查是否存在兩次該元素。如果是，則將其標記爲已使用並增加收集計數。

（僞代碼）：

sort(array) 
count = 0; 
for(i=0;i<size;i++){ 
    if(used[i]) continue; //used elements should not be re-considered 
    for(j=i+1;j<size;j++){ 
    if(array[j]==2*array[i] && !used[j]){ 
     used[j] = true;. 
     count++; 
    } 
    } 
} 

可變計數現在將有集的最大可能數量。

注意尋找2 *陣列[I]數組中也可以通過二進制搜索來實現，但由於該陣列是非常小（尺寸< = 100）

這裏是我的 C++ code因爲那是不必要的問題。 （我已經使用C++標準庫進行排序，您可以使用您選擇的任何排序算法）。

希望這會有所幫助。 乾杯。

Answer 2

Check out this easy solution: 
#include<iostream> 
#include<algorithm> 
#include<stdio.h> 
using namespace std; 
int main() 
{ 
    int t=0; 
    scanf("%d",&t); 
    while(t>0) 
    { 
     t=t-1; 
     int num=0; 
     long long int n[10001]; 
     int count=0; 
     scanf("%d",&num); 
     for(int k=0;k<num;k++) 
     scanf("%lld",&n[k]); 
     sort(n,n+num); 
     for(int i=0;i<num;i++) 
     { 
      if(n[i]==-1)continue; 
      for(int j=i+1;j<num;j++) 
      { 
       if(n[j]==n[i]*2 &&n[i]!=-1 &&n[j]!=-1) 
       { 
        count=count+1; 
        n[i]=-1; 
        n[j]=-1; 
        break; 
        } 


       } 

      } 

     printf("%d\n",count); 

     } 




// getchar(); 
    return 0; 
    }