c - IITKWPCO SPOJ 中的 WA

Question

这是SPOJ的问题

小费鲁达很喜欢玩。如你所知，他只玩数字。所以他得到了n个数字。现在尝试将数字分组到不相交的集合中，每个集合包含两个数字。他可以形成包含两个数的集合当且仅当集合中的小数恰好是大数的一半。

给定n个数，求他最多可以组成多少个集合？

输入

T:测试用例的数量。 (1 <= T <= 100)。

对于每个测试用例:

第一行将包含 n : (1 <= n <= 100)

然后下一行将包含 n 个数字，单个空格分隔。每个数字的范围将在 1 到 10^6 之间。

输出

对于每个测试用例，输出可以组成的最大集合数。

例子

Input:

2

2

1 2

3

1 2 4

Output:

1

1

我的代码::

#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;
 }

有人能指出我哪里出错了或者我遗漏的任何角落测试用例吗？？

Answer 1

你的逻辑有问题。

考虑输入数组为 {2,4,1,8}

的情况

答案应该是 2，因为可以形成集合 {1,2} 和 {4,8}。但是，对于这种情况，您的代码将输出 1(它将 2 与 4 配对，并且只能创建一个集合)。

我已经通过对数组进行排序解决了这个问题，然后对于每个元素，检查该元素是否存在两次。如果是，将其标记为已使用并增加集合计数。

(伪代码):

排序(数组)
计数 = 0；
对于(i=0；i<大小；i++){
  如果(使用[i])继续；//使用过的元素不应该被重新考虑
  对于(j=i+1；j<大小；j++){
     如果(数组[j]==2*数组[i] && !used[j]){
        使用 [j] = 真；。
        计数++；
     }
  }
}

变量 count 现在将拥有最大可能的集合数。

请注意，在数组中搜索 2*array[i] 也可以通过二分查找来实现，但这是不必要的，因为数组非常小(大小 <=100)

这是我的 C++ code 对于这个问题。 (我已经使用c++标准库进行排序，你可以使用你选择的任何排序算法)。

希望这对您有所帮助。 干杯。