首页 > ACM题库 > HDU-杭电 > hdu 2231 I can do it better待解决[解题报告]C++
2014
01-04

hdu 2231 I can do it better待解决[解题报告]C++

I can do it better

问题描述 :

ACboy is playing a new stone game. There’s a rectangular grid board, and some stones placed at the initial location Bi(Xi, Yi) and the targets are at the location Si(Pj, Qj), the time that moving between them is Di,j = |Xi – Pj| + |Yi – Qj| + 1 minutes. And at different places may have different stones, and different target places have different capacity. In the following picture, B1,2,3 stands for the initial places, S1,2,3,4 stands for the target places. In detail, B1(5) means there are 5 stones at this location, S2(4) means you can move at most 4 stones to this target location.

The one who moves the stones from the initial places to the target places using less time will win. So ACboy now telling you his play plan, and you should tell hime whether his plan is the best, or he can do it better.

输入:

The input file consists of The game board description and the play plan description. The first line of the input file consists of two numbers N and M separated by a space. N (1 <= N <= 100) is a number of initial places(numbered from 1 to N). M (1 <= M <= 100) is a number of target places(numbered from 1 to M).

The following N lines describe initial places. Each line contains there integer numbers Xi, Yi, and Bi separated by spaces, where Xi, Yi (-1000 <= Xi, Yi <= 1000) are the coordinates of initial places, and Bi (1 <= Bi <= 1000) is the number of stones at this location.

The description of initial places is followed by M lines that describe target places. Each line contains three integer numbers Pj, Qj, and Cj separated by spaces, where Pi, Qi (-1000 <= Pj, Qj <= 1000) are the coordinates of the target places, and Cj (1 <= Cj <= 1000) is the capacity of this place.

The description of the play plan follows on the next N lines. The play plan of ith initial place consists of M integer numbers Ei,j separated by spaces. Ei,j (0 <= Ei, j <= 1000) is a number of stones that shall move from the ith initial place to the jth target place.

The plan in the input file is guaranteed to be valid. Namely, B1+B2+….+Bn <= S1+S2+….+Sn.

Process to the end of file.

输出:

The input file consists of The game board description and the play plan description. The first line of the input file consists of two numbers N and M separated by a space. N (1 <= N <= 100) is a number of initial places(numbered from 1 to N). M (1 <= M <= 100) is a number of target places(numbered from 1 to M).

The following N lines describe initial places. Each line contains there integer numbers Xi, Yi, and Bi separated by spaces, where Xi, Yi (-1000 <= Xi, Yi <= 1000) are the coordinates of initial places, and Bi (1 <= Bi <= 1000) is the number of stones at this location.

The description of initial places is followed by M lines that describe target places. Each line contains three integer numbers Pj, Qj, and Cj separated by spaces, where Pi, Qi (-1000 <= Pj, Qj <= 1000) are the coordinates of the target places, and Cj (1 <= Cj <= 1000) is the capacity of this place.

The description of the play plan follows on the next N lines. The play plan of ith initial place consists of M integer numbers Ei,j separated by spaces. Ei,j (0 <= Ei, j <= 1000) is a number of stones that shall move from the ith initial place to the jth target place.

The plan in the input file is guaranteed to be valid. Namely, B1+B2+….+Bn <= S1+S2+….+Sn.

Process to the end of file.

样例输入:

2 1
0 0 5
1 1 5
2 2 5
5
0

样例输出:

I can do it better

Hint: in the case, ACboy moves the 5 stones from B1 at (0,0) to S1 at (2,2), and it costs him 5*5 = 25 minutes, 
but if he move the 5 stones from B2 at (1,1) to S1 at (2,2), it will only takes him 3*5 = 15 minutes, so his plan is not the best.


  1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

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