私はの配列を持っていWます0..N-1
それらを 2 つのセットに分割する必要があります: SayKとN-KElements です。
ただし、条件は次のとおりです。sum(N-K)-sum(K)最大にする必要があります。
どうすればこれにアプローチできますか?
私はこれをやってみました：配列を並べ替え - std::sort(W,W+N)、そして：
for(int i=0; i<K; ++i) less+=W[i];
for(int i=K; i<N; ++i) more+=W[i];
その後more-less
しかし、これが最適な方法だとは思いませんし、場合によっては間違っているかもしれません。
ありがとう。
更新：
との差が最大になるようなK要素を選択する必要があります。Wsum(k elements)sum(remaining elements)
を使用して実行できますmax heap。O(n + n log k)時間
size の最大ヒープを作成しますk。k配列の最下位の要素を見つけました。rootof ヒープは、ヒープ内の最上位の要素になります。Make a heap of first k elements.
配列を反復処理します。配列要素をroot最大ヒープと比較します。ルートよりも小さい場合は、それを置き換えて、ヒープを再度ヒープ化します。これには O(n log k) 時間がかかります。ヒープの要素の合計を見つけます。
これで、配列の残りの要素の合計を見つけて差を得ることができます。( O(n)) 時間
合計時間O(n + n log k)
編集:おそらく、ヒープをトラバースしながら、配列のすべての要素の合計を見つけることができます。これにより時間が節約O(n)され、次の方法で解決できます。O(n log k)