首页 > ACM题库 > HDU-杭电 > HDU 3017-Treasure Division[解题报告]HOJ
2014
02-27

HDU 3017-Treasure Division[解题报告]HOJ

Treasure Division

问题描述 :

Ant Tony and Monkey Luffy have discovered a big treasure.It turns out to be a box of gold coins.There are N gold coins in the box.However,the gold coins are not all the same.Every gold coin has a value Vi.Now they wants to divide this big treasure into two halves.The number of gold coin differ in two half must be no more than one.Tony and Luffy wants to know the fairest division,ie,the division which minimize the difference between each parts.

Man Down

输入:

Input contains multiple cases.Test cases are separated by several blank lines.

Each test case starts with a integer N(1<=N<=30) ,indicating that there are N gold coins int the treasure box.Followed by one line contain N integer,the ith integer vi (1<=vi<=2^30),representing the value of coin i.

输出:

Input contains multiple cases.Test cases are separated by several blank lines.

Each test case starts with a integer N(1<=N<=30) ,indicating that there are N gold coins int the treasure box.Followed by one line contain N integer,the ith integer vi (1<=vi<=2^30),representing the value of coin i.

样例输入:

3
2 2 4
4
1 2 3 6

样例输出:

0
2

Hint
In sample 1,we can divide the 3 gold coins into {1,2},{3}, their difference is 0. In sample 2,we can divide the 4 gold coins into {1,4},{2,3}, their difference is 2,which is also the least difference that could be made.

http://acm.hit.edu.cn/hoj/problem/view?id=3017

#include <stdio.h>
#include <string.h>

int main()
{
    char password[33];

    while (scanf("%s", &password) != EOF)
    {
        if (strcmp(password, "wujiawei") == 0)
        {
            printf("hit\n");
        }
        else
        {
            printf("lose\n");
        }
    }

    return 0;
}

参考:http://blog.csdn.net/epk_lee/article/details/8201595


  1. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  2. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。

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