1

からの質問ですSPOJ

小さなフェルーダはとても遊ぶのが好きです。ご存知のように、彼は数字だけで遊んでいます。したがって、彼には n 個の数字が与えられます。次に、それぞれが 2 つの数値を含む互いに素なコレクションに数値をグループ化しようとします。コレクション内の小さな数が大きな数のちょうど半分である場合、彼は 2 つの数を含むコレクションを形成できます。

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} の場合を考えてみましょう

コレクション {1,2} と {4,8} を形成できるため、この答えは 2 になります。ただし、この場合、コードは 1 を出力します (2 と 4 がペアになり、1 つのコレクションしか作成できません)。

配列をソートすることでこの問題を解決し、各要素について、その要素が2回存在するかどうかを確認します。はいの場合は、使用済みとしてマークし、コレクションの数を増やします。

(疑似コード): 

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] の検索はバイナリ検索でも実装できることに注意してください。

これが問題の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 に答える