Question

杭电ACM 1051 求思路好像要用贪心法,能举例更好

Answer 1

把所有的木头按照长度大的在前面,长度小的在后面,长度一样的重的在前面,轻的在后面进行排序.

然后从第一个开始加工,setup time加1,如果一个被加工了,我们往后面看,把最近的下一个能直接加工的拿去加工,如此类推,直到最后.然后重新加工最前面那个未被加工的木头,setup time加1,如此类推直到所有木头都加工过为止

#include

#include

#include

typedef struct

{

int len;

int weight;

} wood;

int cmp(const void* a, const void* b)

{

wood* wa = (wood*)a;

wood* wb = (wood*)b;

if(wa->len!=wb->len)

return wb->len - wa->len;

return wb->weight - wa->weight;

}

int main()

{

int T,i,N,setup,m,j;

wood w[5000];

int used[5000];

scanf("%d",&T);

while(T--)

{

scanf("%d",&N);

for(i=0;i