首页 > ACM题库 > HDU-杭电 > hdu 2218 Don’t be angry待解决[解题报告]C++
2014
01-04

hdu 2218 Don’t be angry待解决[解题报告]C++

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,比楼主的要快。

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  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;
    }