2014
01-04

# Don’t be angry

Wiskey buys a cake and wants to eat with Michelle. The cake is very delicious with many chocolates on it.
The cake is big; Wiskey need cut it to 6 pieces.
Michelle is a perfectionist and she sets perfect standard for Wiskey that each piece must contains the same weight of chocolates.
At first the cake may be not perfect, so Wiskey get some chocolate sticks, but the chocolate stick is too long, it will occupy adjacent two pieces and add same weight on the adjacent two pieces.
You can assume Wiskey have infinite various weight chocolate sticks.
Quick, Help Wiskey! Michelle is beginning to be angry.

First line will contain one integer means how many cases will be follow.
Each line will contain six integers means the weight of chocolates at first.
All integers range in signed 32 bits.

First line will contain one integer means how many cases will be follow.
Each line will contain six integers means the weight of chocolates at first.
All integers range in signed 32 bits.

4
1 1 1 1 1 1
1 1 1 1 1 0
1 1 1 1 0 0
2 1 0 0 1 2

YES
NO
YES
YES

1. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

3. #include <cstdio>
#include <algorithm>

struct LWPair{
int l,w;
};

int main() {
//freopen("input.txt","r",stdin);
const int MAXSIZE=5000, MAXVAL=10000;
LWPair sticks[MAXSIZE];
int store[MAXSIZE];
int ncase, nstick, length,width, tmp, time, i,j;
if(scanf("%d",&ncase)!=1) return -1;
while(ncase– && scanf("%d",&nstick)==1) {
for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
for(time=-1,i=0;i<nstick;++i) {
tmp=sticks .w;
for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
if(j==time) { store[++time]=tmp; }
else { store[j+1]=tmp; }
}
printf("%dn",time+1);
}
return 0;
}