1

n組の整数xとyが与えられた問題のセクションを解くには、異なるx/yがいくつあるかを見つける必要があります。(小数点以下の正確な値)

1.

もちろん、以前のすべてのペアを反復処理して、同じx/y値が以前に発生したかどうかを確認することもできますが、それには(n^2)/2時間かかると思います。

ハッシュ テーブルを使用してみましたが、float 値ではうまく機能しないようです。たぶん、非常に優れたハッシュ関数で機能するでしょう。

2.

xとyが整数であることを考慮して、問題に対して別のアプローチを試みました。

  • 各ペアの最大公約数を計算します
  • xとyを GCD で割る

  • 行列 m[max_value_of_x][max_value_of_y] を使用して、次のようにします。

    if ( m[x][y] ) { ; } else { m[x][y] = 1 ; cnt++ ; }

  • すべてのペアに対してこれを行った後、cntは異なる float 値の数になるはずです。

これはかなりの時間で実行できると思いますが。それは間違いなくスペース効率が悪いです。実際の問題では、xとyの最大値は 1000 ですが、割り当てられたメモリはかなり少なくなっています。

4

3 に答える 3

1

set を使用した MBo のソリューションから:

struct cmp_div {
    bool operator ()(const std::pair<int, int>& xy1, const std::pair<int, int>& xy2) const {
        // x1/y1 < x2/y2
        return xy1.first*xy2.second < xy2.first*xy1.second;
    }
};

std::set<std::pair<int, int>, cmp_div> c;
c.emplace(6, 2);
c.emplace(9, 3);
std::cout << c.size(); // == 1
于 2014-02-23T13:56:59.517 に答える