bin packing2

입력 출력같음 (빈갯수가 2^n아님)

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

int arr[100];

int tree[100];

int offset;// 2 * s - 1

int s; // 2^ (c(log2(n)) -1)

int lowext; // 2*( (n-1) - (s-1))

void init(int n, int size)

{

int i=0;

int k;

int p;

double l;

int ce;

l=log( (double)n ) / log( (double)2 );

ce = ceil(l);

s = pow((double)2, ( ce -1 ));

offset = 2*s-1;

lowext = 2*((n-1) - (s-1));

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

{

arr[i] = size;

}

if (n%2 == 0)

{

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

{

if (k%2==1)

{

if (k<=lowext)

p = (k+offset) / 2;

else

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

tree[p] = k;

}

}

}

else

{

for (k=1;k<=lowext; k+=2)

{

if (k<=lowext)

p = (k+offset) / 2;

else

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

tree[p] = k;

}

for (k=lowext +2; k<=n; k+=2)

{

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

//p= (s+(k-lowext)) /2;

tree[p] = k;

}

}

/*

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

if (i%2 == 1)

tree[ (i+n-1)/2 ] = i;

}

*/

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

{

tree [i] = tree[i*2];

}

}

int main(void)

{

int i,j;

int n;

int cnt,size;

//빈개수, n(오브젝트 개수), 빈사이즈 

FILE* f = fopen ("input2.txt","r");

fscanf (f,"%d %d %d",&cnt,&n,&size);

// arr = (int *)malloc(sizeof(int)*cnt+1);

// tree = (int *)malloc(sizeof(int)*cnt);

init(cnt,size);

for (i=1;i<cnt;i++)

{

printf ("%d ",tree[i]);

}

for (i=0;i<n;i++)

{

int a;

int idx;

int parent;

fscanf (f,"%d",&a);

idx = 1;

while(1)

{

if ( arr[tree[idx]] >= a)

{

idx = idx*2;

if (idx >=cnt)

{

idx /=2;

break;

}

if (arr[tree[idx]]<a)

{

idx /=2;

idx = idx*2+1;

}

if (idx >=cnt)

{

idx /=2;

break;

}

/*

if (idx *2 >=cnt)

break;

if (arr[tree[idx*2]] <a)

{

if (idx*2+1 >= cnt)

break;

idx = idx*2+1;

}

else

{

idx = idx*2;

}

*/

}

else

{

idx = idx*2+1;

if (idx*2+1 >= cnt)

{

idx = (idx-1)/2;

break;

}

}

}

if (tree[idx]%2 == 0 && arr[tree[idx]-1] >= a)

{

arr[tree[idx]-1] -=a;

parent = idx-1;

}

else

{

arr[tree[idx]] -= a;

parent = idx;

}

/*

if (arr[tree[idx]] >a)

arr[tree[idx]] -= a;

else

arr[tree[idx]] -= a;

*/

/*

if (tree[idx] %2 == 0)

{

if (arr[tree[idx]] > arr[tree[idx]-1])

tree[idx] = tree[idx];

else

tree[idx] = tree[idx]-1;

}

else

{

if (arr[tree[idx]] > arr[tree[idx]+1])

tree[idx] = tree[idx];

else

tree[idx] = tree[idx]+1;

}

*/

while(1)

{

int lc;

int rc;

lc = parent*2;

rc = parent*2+1;

if (lc > cnt-1)

{

if (lc>offset)

{

lc=lc-offset;

}

else

{

//lc=lc-lowext;

lc=(lc+lowext - (cnt-1));

}

}

else

{

lc = tree[lc];

}

if (rc > cnt-1)

{

if (rc>offset)

{

rc=rc-offset;

}

else

{

//rc=rc-lowext;

rc=(rc+lowext - (cnt-1));

}

}

else

{

rc = tree[rc];

}

if (arr[lc] >= arr[rc])

{

tree[parent] = lc;

}

else

{

tree[parent] = rc;

}

/*

if (parent*2>cnt-1)

{

tree[parent] = 

tree[parent] = arr[parent*2 - (offset)] >= arr[parent*2-(offset)+1] ? parent*2 - (offset) : parent*2-(offset)+1;

}

else

{

lc = arr[tree[parent*2]];

if (parent*2+1 > cnt-1)

rc =  (parent*2+1)-lowext ;

else

rc = tree[parent*2+1];

tree[parent] = (lc >= arr[rc]) ? tree[parent*2] : rc;

}

*/

parent/=2;

if (parent<1)

break;

}

printf ("\nret : %d",a);

for (j=1;j<cnt;j++)

{

// printf ("%d ",tree[j]);

}

printf ("\n");

for (j=1;j<=cnt;j++)

{

printf ("%d ",arr[j]);

}

printf ("\n");

}

}