1

このパズルを解こうとしています: Shipping Coding Puzzle . これは私がこれまでに思いついたコードです:

#include <fcntl.h>
#include <sys/mman.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <sstream>
#include <set>
using namespace std;
struct Container
{
    Container(int c, int w) : cost(c), weight(w){}
    int cost;
    int weight;
    bool operator<(const Container& c) const
    {
        return double(cost)/weight < double(c.cost)/c.weight;
    }
};
int main(int argc, char** argv)
{
    int fd = open(argv[1], O_RDONLY);
    char* pContent = (char*)mmap(NULL, 128 * sizeof(int), PROT_READ, MAP_PRIVATE, fd, 0);
    pContent += 8;
    stringstream ss(pContent);
    int unload = 0;
    ss >> unload;
    set<Container> containers;
    int cost = 0, weight = 0;
    while(ss >> cost)
    {
        ss >> weight;
        containers.insert(Container(cost, weight));
    }

    const Container& best = *containers.begin();
    cost = best.cost * ceil(double(unload)/best.weight);
    printf("%d\n", cost);
    return 0;
}

このロジックにはいくつかのバグがあるかもしれません。しかし、私の質問はロジックとは関係ありません。このコードを送信すると、正常に実行されますが、マイナー ページ フォールトの数が409. リーダー ボードを見ると、誰かがマイナー ページ フォールトのある C++ コードを提出しています69。これらのマイナーなページ フォールトを制御する方法はありますか? いくつかの g++ フラグを使用している可能性がありますか? 現在、私のメイク ファイルは非常に単純です: g++ -o MyExe MyExe.cc.

4

1 に答える 1

2

これらを判断するために Gild が使用するアルゴリズムとランタイム環境に翻弄されます。コンパイラ フラグはおそらくニシンだと思います。「リリースモード」でサブミットすると、-O2 または -O3 がオンになるのではないかと思います。

メモリ使用の最適化、おそらくメモリの局所性の問題だと思います。たとえば、その文字列ストリームとセットは非常に高価になる可能性があります。あなたの場合、私は別の方法があるかどうかを調べ始めます。おそらく、より調整されたアルゴリズムを使用します。

于 2011-10-30T06:15:50.850 に答える