1

今日、この問題に遭遇しました。これではa[]、昇順でソートされた配列が与えられ、数値の合計を見つけて、型(負でない)の追加の整数の最小数を見つける必要があります。存在するすべての整数の合計が、ある整数(が負ではない) に等しくなるように必要です。2a1, 2a2, 2a3, ..., 2an2ll2k - 1kk

例えば：

入力は、最初の行の整数 n で構成されます。2 番目の入力行には、スペースで区切られた n 個の整数 a(1)、a(2)、...、a(n) が含まれます。

例 1:
3
0 1 2

この場合の答えは 0 です。2 0 +2 1 +2 2 = 7 は、k=3 に対して 2 k -1 の形式になっているからです。

例 2:
3
2 4 5

この場合の答えは 2 2 +2 4 +2 5 =52 なので 3 で、2 k -1 を作るには 63 なので、3 項として 2 0 ,2 1 ,2 3が必要です。

この問題に取り組み、合計を見つけてから、バイナリ表現の 1 の数を数え、 equals と答えmax(a[i])-countました。

しかし、私が得る問題は、問題の与えられた制約です
1 ≤ n ≤ 10^5
0 ≤ a[i] ≤ 2*10^9

誰か助けてくれませんか？この問題は私がプログラミング コンテストで得たもので、解決策は 2.6 MB のメモリで受け入れられました。したがって、2*10^9 ビットの配列ビットを格納または取得することは、より良い方法ではありません。別のアプローチまたはアイデアがあると思います。

4

2 に答える 2

0

あなたがする必要があるのは、ビット配列を操作することです。

i <= 2*10 9 (20 億)が必要です。20 億ビットを表すには、約 256MB のメモリが必要です (各バイトには 8 ビットが格納されます)。のような関数を提供する便利な抽象化レイヤーを作成する必要がある場合があります.get(int n)。.set(int n)これは、そのビット配列のビットを読み取って保存します。

配列を割り当てるには、次を使用しますmalloc。

typedef byte unsigned char;
// 256MB, enough for 2 billion bits
byte * bit_array = malloc(256*1024*1024);

// or use calloc, which initializes to 0:
byte * bit_array = calloc(256*1024*1024, 1);

ビット n を設定するには、次の割り当てを使用します。

bit_array[n/8] |= 1 << (n % 8);

ビット n を取得するには、次の式を使用します。

(bit_array[n/8] >> (n % 8)) & 1

アルゴリズムは次のようになります。

  • 任意の最大長のビット配列をすべて 1 セット作成します。
  • すべての a iをループし、そのビット配列の i 番目のビットを 0 に設定します。
  • まだ 1 に設定されているビット数を数えます。それが答えです。
于 2013-10-26T22:22:17.497 に答える