首页 > ACM题库 > HDU-杭电 > hdu 2401 Baskets of Gold Coins[解题报告]C++
2014
01-26

hdu 2401 Baskets of Gold Coins[解题报告]C++

Baskets of Gold Coins

问题描述 :

You are given N baskets of gold coins. The baskets are numbered from 1 to N. In all except one of the baskets, each gold coin weighs w grams. In the one exceptional basket, each gold coin weighs w-d grams. A wizard appears on the scene and takes 1 coin from Basket 1, 2 coins from Basket 2, and so on, up to and including N-1 coins from Basket N-1. He does not take any coins from Basket N. He weighs the selected coins and concludes which of the N baskets contains the lighter coins. Your mission is to emulate the wizard’s computation.

输入:

The input file will consist of one or more lines; each line will contain data for one instance of the problem. More specifically, each line will contain four positive integers, separated by one blank space. The first three integers are, respectively, the numbers N, w, and d, as described above. The fourth integer is the result of weighing the selected coins.

N will be at least 2 and not more than 8000. The value of w will be at most 30. The value of d will be less than w.

输出:

The input file will consist of one or more lines; each line will contain data for one instance of the problem. More specifically, each line will contain four positive integers, separated by one blank space. The first three integers are, respectively, the numbers N, w, and d, as described above. The fourth integer is the result of weighing the selected coins.

N will be at least 2 and not more than 8000. The value of w will be at most 30. The value of d will be less than w.

样例输入:

10 25 8 1109
10 25 8 1045
8000 30 12 959879400

样例输出:

2
10
50

2012-01-02 19:55:02

地址:http://acm.hdu.edu.cn/showproblem.php?pid=2401

题意:有1-N一共N个篮子,每个里面有很多金币。每个金币的重量是w,但是其中有一个篮子金币的重量只有w-d。现在从第一个篮子拿1个金币,第二个拿2个。。。第n-1个篮子拿n-1个。第n个不拿。把拿出来的金币称重。问金币轻的篮子编号是多少。

mark:不知道第二组sample为什么可以是10。。。诡异。

代码:

# include <stdio.h>


int main ()
{
    int n, w, d, rst, ans ;
    while (~scanf ("%d%d%d%d", &n, &w, &d, &rst))
    {
        ans = (n*(n-1)*w/2-rst) / d ;
        printf ("%d\n", (ans == 0) ? n : ans ) ;
    }
    return 0 ;
}

解题转自:http://www.cnblogs.com/lzsz1212/archive/2012/01/07/2315447.html


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

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。