首页 > ACM题库 > HDU-杭电 > Hdu 1146 Ferry Loading III 模拟 [解题报告] C++
2013
12-02

Hdu 1146 Ferry Loading III 模拟 [解题报告] C++

Ferry Loading III

问题描述 :

Before bridges were common, ferries were used to transport cars across rivers. River ferries, unlike their larger cousins, run on a guide line and are powered by the river’s current. Cars drive onto the ferry from one end, the ferry crosses the river, and the cars exit from the other end of the ferry.
There is a ferry across the river that can take n cars across the river in t minutes and return in t minutes. A car may arrive at either river bank to be transported by the ferry to the opposite bank. The ferry travels continuously back and forth between the banks so long it is carrying a car or there is at least one car waiting at either bank. Whenever the ferry arrives at one of the banks, it unloads its cargo and loads up to n cars that are waiting to cross. If there are more than n, those that have been waiting the longest are loaded. If there are no cars waiting on either bank, the ferry waits until one arrives, loads it (if it arrives on the same bank of the ferry), and crosses the river. At what time does each car reach the other side of the river?

输入:

The first line of input contains c, the number of test cases. Each test case begins with n, t, m. m lines follow, each giving the arrival time for a car (in minutes since the beginning of the day), and the bank at which the car arrives (“left” or “right”). For each test case, output one line per car, in the same order as the input, giving the time at which that car is unloaded at the opposite bank. Output an empty line between cases.

输出:

You may assume that 0 < n, t, m ≤ 10000. The arrival times for each test case are strictly increasing. The ferry is initially on the left bank. Loading and unloading time may be considered to be 0.

样例输入:

2
2 10 10
0 left
10 left
20 left
30 left
40 left
50 left
60 left
70 left
80 left
90 left
2 10 3
10 right
25 left
40 left

样例输出:

10
30
30
50
50
70
70
90
90
110

30
40
60

#include<iostream>

using namespace std;

int main()

{

	int t, c, n, m, i, time, ln[2], lt[2], ont, bt, temp, llt;

	bool bleft, tleft;

	char ch[10];

	cin >> c;

	while (c--)

	{

		ln[0] = ln[1] = lt[0] = lt[1] = 0, bleft = 1, ont = 0, bt = 0;

		cin >> n >> t >> m;

		for (i = 0; i < m; i++)

		{

			scanf("%d%s", &time, ch);

			if (ch[0] == 'l')
				tleft = 1;
			else
				tleft = 0;

			if (bt + ont <= time)
			{
				bleft = (bleft + ont / t) % 2;
				bt = time;
				if (bleft == tleft)
				{
					ln[tleft] = 0;
					ont = t;
				}
				else
				{
					ln[tleft] = 1;
					ont = 2 * t;
				}
				ln[(tleft + 1) % 2] = 0;
				lt[0] = lt[1] = 0;
				printf("%d/n", bt + ont);
			}
			else
			{
				llt = 0;
				if (time >= bt + t)
				{
					temp = (time - bt) / t;
					bt += temp * t;
					ont -= temp * t;
					bleft = (bleft + temp) % 2;
					if (temp % 2) //难点
						lt[bleft]--;
					lt[0] -= temp / 2;
					lt[1] -= temp / 2;
					lt[bleft] -= temp % 2;
					lt[bleft]++; //问题所在
					if (lt[0] < 0)
					{
						ln[0] = 0;
						lt[0] = 0;
					}
					if (lt[1] < 0)
					{
						ln[1] = 0;
						lt[1] = 0;
					}

				}

				if (time > bt)

					llt = 2 * t;

				ln[tleft]++;

				if (bleft == tleft)
				{

					cout << bt + 2 * t * lt[tleft] + t + llt << endl;

					if (2 * t * lt[tleft] + t + llt > ont)

						ont = 2 * t * lt[tleft] + t + llt;

				}

				else
				{

					cout << bt + 2 * t + 2 * t * lt[tleft] << endl;

					if (2 * t * lt[tleft] + 2 * t > ont)

						ont = 2 * t * lt[tleft] + 2 * t;

				}

				if (ln[tleft] == n)
				{

					ln[tleft] = 0;

					lt[tleft]++;

				}

			}

		}

		if (c)

			printf("/n");

	}
	return 0;

}

 


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

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