1

这是一个问题SPOJ

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

给定 n 个数字，找出他最多可以形成多少个集合？

输入

T：测试用例的数量。（1 <= T <= 100）。

对于每个测试用例：

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

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

输出

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

例子

输入：

2

2

1 2

3

1 2 4

输出：

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

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

4

2 回答 2

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

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

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

这是我解决问题的C++ 代码 。（我使用了 c++ 标准库进行排序，您可以使用您选择的任何排序算法）。

希望这可以帮助。干杯。

于 2013-09-13T19:05:21.823 回答
0 
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;
    }
于 2015-05-19T09:15:54.490 回答