Tournament : Bin Packing Problem

asdf.cpp

#include <iostream>

#include <fstream>

using namespace std;

int n, m, size;

int tree[1000];

int player[1000];

void doBin(int input)

{

int head = 1;

while(head < n) // 찾아가기

{

if(head * 2 >= n)

break;

//if(player[tree[head * 2]] >= player[tree[head * 2 + 1]]) // 왼쪽이 더 크면

if(player[tree[head * 2]] >= input) // 왼쪽이 더 크면

{

head *= 2;

}

else

{

head = head * 2 + 1;

}

}

if(player[head * 2 - (n - 1)] >= input) // 왼쪽이 더 크면

{

player[head * 2 - (n - 1)] -= input;

//tree[head] = head * 2 - (n - 1); // 왼쪽이 새엄마

}

else

{

player[head * 2 - (n - 1) + 1] -= input;

//tree[head] = head * 2 - (n - 1) + 1; // 오른쪽이 새엄마

}

// 리프노드

if(player[head * 2 - (n - 1)] >= player[head * 2 - (n - 1) + 1]) // 왼쪽이 더 크면

{

tree[head] = head * 2 - (n - 1); // 왼쪽이 새엄마

}

else

{

tree[head] = head * 2 - (n - 1) + 1; // 오른쪽이 새엄마

}

head = head / 2;

while(head > 0) // 올라가면서 복구

{

if(player[tree[head * 2]] >= player[tree[head * 2 + 1]]) // 왼쪽이 더 크면

{

tree[head] = tree[head * 2]; // 왼쪽이 새엄마

}

else

{

tree[head] = tree[head * 2 + 1]; // 오른쪽이 새엄마

}

head = head / 2;

}

for(int i = 1; i <= n; i ++)

{

cout << player[i] << " ";

}

cout << endl;

}

void init()

{

int p = -1;

// 인터널 노드 아래 초기화

for (int k = 1; k <= n; k += 2)

{

p = (k + n - 1) / 2;

tree[p] = k;

}

for(int k = (n - 1) / 2 ; k > 0; k --)

{

tree[k] = tree[k * 2];

}

}

int main()

{

fstream fin("input.txt");

fin >> n >> m >> size;

for(int i = 1; i <= n; i ++)

{

player[i] = size;

}

init();

for(int i = 0; i < m; i ++)

{

int input;

fin >> input;

doBin(input);

}

for(int i = 1; i <= n; i ++)

{

cout << player[i] << " ";

}

cout << endl;

return 0;

}