首页 > ACM题库 > HDU-杭电 > hdu 2943 Special Robot待解决[解题报告]C++
2014
02-24

hdu 2943 Special Robot待解决[解题报告]C++

Special Robot

问题描述 :

Bob invented a special kind of robot controlled by a remote controller. The interesting thing is that the robot can only move in a 2-dimentional plane which is vertical to the ground. Now we assume the vertical plane can be shown in Figure 1.

Now Bob wants to conduct a performance for his robot. The situation can be described as follows: n balloons stay still on the ground; all of these balloons have an initial position whose Y-coordinates are 0.
Each balloon will move up at certain time. The initial position of the robot is at (0, 0) and if the robot is at position (x, y) at time t, then it can only move to position (x, y-1) or position (x+1, y+1) in a unit time (the robot con not stay still at a position). Its task is to collect as more balloons as possible when it gets to the destination (K,0).

When the robot is moving on the plane, balloons are continuously rising on its path from the ground. Each balloon can reach a unit height in a unit time.
When the robot meets a balloon, it collects the balloon. The situation can be described as the following three examples which are shown in Figure 2:

Example 1: At time t, the robot is at position (x, y), and a balloon is at position (x, y-2). The robot moves down and the balloon moves up; then at time t+1, the robot and the balloon meet at position (x, y-1), so the balloon can be collected by the robot ( which is shown in Figure 2(a)).

Example 2: At time t, there is a balloon at position (x, y-1) and the robot stands at position (x, y). Because the balloon always moves up and the robot can move down, so the robot can collect this balloon because they will meet at some point between position (x, y-1) and (x, y) during their movement (which is shown in Figure 2(b)).

Example 3: At time t, a balloon is at position (x+1, y) and the robot is at position (x, y). Because the robot can arrive at position (x+1, y+1) while the balloon can move up to the same position, the robot could collect the balloon at time t+1 (which is shown in Figure 2(c)).

Maybe it is too easy a problem to control one robot, so Bob intends to control two robots simultaneously.
You need to help him to calculate the maximum balloons these two robots can collect when they get to the destination.

It is possible that the two robots get to the same position at the same time. Note that one balloon could not be collected by two robots and the balloons staying on the ground could not be collected either.

Robot should not move to the underground (y < 0).

输入:

The input contains several cases. For each case, the first line gives the value of n (0 ≤ n ≤ 10,000) and K (1 ≤ K ≤ 100) followed by n lines in which each contains two integers x (1 ≤ x ≤ K) and t (0 ≤ t ≤ 1000).

The first integer indicates the position of a balloon and the other indicates the beginning time for it to rise. In the value of n and K, n is the number of balloons and K is the x-coordinate of the destination. The input is ended by two zeros.

输出:

The input contains several cases. For each case, the first line gives the value of n (0 ≤ n ≤ 10,000) and K (1 ≤ K ≤ 100) followed by n lines in which each contains two integers x (1 ≤ x ≤ K) and t (0 ≤ t ≤ 1000).

The first integer indicates the position of a balloon and the other indicates the beginning time for it to rise. In the value of n and K, n is the number of balloons and K is the x-coordinate of the destination. The input is ended by two zeros.

样例输入:

3 2
1 1
1 1
1 2
7 4
2 0
2 3
3 4
3 0
3 2
4 0
1 1
0 0

样例输出:

2
6


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

  2. 算法是程序的灵魂,算法分简单和复杂,如果不搞大数据类,程序员了解一下简单点的算法也是可以的,但是会算法的一定要会编程才行,程序员不一定要会算法,利于自己项目需要的可以简单了解。

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。