首页 > ACM题库 > HDU-杭电 > hdu 3919 Little Sheep待解决[解题报告]C++
2015
04-14

hdu 3919 Little Sheep待解决[解题报告]C++

Little Sheep

问题描述 :

  As we all know, sheep are very lazy, they don’t like move and just want to enjoy delicious food. So, Mr. LittleSheep who is in charge of a farm which owns lots of sheep is extremely tired in feeding these sheep. Mr. LittleSheep’s farm is like a circle consists of n corrals, each corral has a certain number of sheep, and every corral has a door for feeding. When it comes to feeding time, Mr. LittleSheep has to decide in which orders should he open those doors, because he can just open one door every time, otherwise these tricky sheep would run away. When the door is opened, the lazy sheep whose distance to the open door less or equal to k will go out, the distance to the open door is defined by the number of corrals between the open door and sheep’s corral. Due to the narrow door, it is allowed just one sheep to leave per minute. In order to let other lazy sheep get fed, Mr. LittleSheep has to move to anther corral to open the door, we assume the distance between the current corral and the destination is D, and the maximum amount of sheep among the rest corrals is M, then it takes D*M minute to move. (Because every step Mr. LittleSheep moves, it takes M minute to calm down the largest group of sheep), Now the question is how Mr. LittleSheep should move to use the least time for feeding all these lazy sheep. Mr. LittleSheep always started his work at 1st corral.
Beiju

输入:

The first line is two integers n, k which indicates the number of corrals and the longest distance which sheep are willing to go.
  The second line is n positive integers which describe the amount of sheep in each corral. The ith number a[i] is the number of sheep in ith corral.
(1 <= a[i] <= 10000)(1 <= n <= 2000, 1 <= k <= 500 ,k <= n/2 )

输出:

The first line is two integers n, k which indicates the number of corrals and the longest distance which sheep are willing to go.
  The second line is n positive integers which describe the amount of sheep in each corral. The ith number a[i] is the number of sheep in ith corral.
(1 <= a[i] <= 10000)(1 <= n <= 2000, 1 <= k <= 500 ,k <= n/2 )

样例输入:

6 1
4 1 2 3 1 3

样例输出:

21


  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. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮