3

さて、私はアイテムのベクトルに並べ替えを使用しようとしたので、2つの補助アイテムのサイズは<=2dです。だからここに私の試みがあります：

struct item{
    long number;
    long size;
};

// d is global variable.
bool check(const item& x, const item& y)
{
    return ((x.size + y.size) <= (2 * d));
}

// Items is a vector of item.
sort(items.begin(), items.end(), check);

私は何を間違っているのですか、それともそのような条件を使用してソートすることさえ不可能ですか？

4

3 に答える 3

5

そのような条件を使ってソートすることさえ不可能ですか？

いいえ。の比較対象者は、あなたが明らかに満たしていない厳密な弱順序sortの基準を満たさなければなりません（たとえば、それは非反射的ではありません）。

于 2011-02-27T19:08:17.780 に答える
2

この問題は、O（N log N）時間では解決できません。それがNP困難であるかどうかはわかりませんが、それは非常に重要です。コードで表現されている問題を解決するプログラムには、指数関数的な時間がかかると言っても過言ではありません。そのようなプログラムがあります：私はそれをいじって線形オプティマイザーに接続することができると思います。

標準ライブラリ関数では、一般的なソリューションへの道のほとんどを取得することはできません。O（N log N）より遅い標準ライブラリ関数はなく、扱いにくい問題を解決するものもありません。

この問題は、たとえば、すべてがにsize等しい場合は手に負えません10 * d。

于 2011-02-27T19:18:10.377 に答える
0

sort（）メソッドを間違って使用しています。

STLソートは、要素のリストを並べ替えるために使用されます。「注文」の場合、次のような条件を満たす必要があります。

  1. check（A、B）== false AND A！= Bの場合、check（B、A）はtrueを返します。
  2. check（A、B）== false AND check（B、C）== false AND A、B、Cが異なる場合、check（A、C）はfalseを返します。

STLのsort（）を使用できる場所については、アイテムのリストSと、アイテムを配置する順序を指定すると、次のようになります。

  1. Sの項目の順序が変わっても、出力の順序は同じままである必要があります。
  2. 出力は一意です。
  3. 出力順序のすべての項目には、厳密な半順序関係である何らかの関係があります。

この場合、おそらくあなたはあなたのために働くチェック関数を書くことができます:)

于 2011-02-27T19:10:07.390 に答える