POJ 2674 Linear world 题解 《挑战程序设计竞赛》

POJ 2674 Linear world

线性世界：一条线上N只蚂蚁，每只蚂蚁速度固定，方向和坐标不同，碰头后掉头，求最后掉下去那只蚂蚁的名字。

3.2常用技巧精选（一）

弹性碰撞

首先想象整个世界只有一只蚂蚁，于是可以计算出爬行时间最长的那一只，把它记下来。接着考虑其他蚂蚁，碰头时想象为两只蚂蚁交换姓名，擦肩而过即可。那么问题就剩下，统计这只蚂蚁跟多少只蚂蚁交换了姓名，最后交换的那一只就是答案了。那么到底跟谁交换了姓名呢？由于蚂蚁速度都一样，于是在前进路线上只会与那些逆行的蚂蚁碰头。统计出来后问题就解决了，需要注意答案的格式是截断小数不是四舍五入。

#include <iostream>
#include <string>
#include <algorithm>
#include <iomanip>
using namespace std;
#define MAX_N 32000 + 16

struct Inhabitant
{
	double position;
	string name;
	bool operator < (const Inhabitant& other) const
	{
		return abs(position) < abs(other.position);
	}
};
Inhabitant ih[MAX_N];

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int N;
	while (cin >> N && N)
	{
		double L, V;
		cin >> L >> V;
		for (int i = 0; i < N; ++i)
		{
			char pn;
			cin >> pn >> ih[i].position >> ih[i].name;
			if (pn == 'n' || pn == 'N')
			{
				ih[i].position = -ih[i].position;
			}
		}
		// 输入结束
		sort(ih, ih + N);
		double max_d = 0.0;	// 离端点的最远距离
		int id = 0;			// 对应的居民
		bool right = true;	// 该居民是否往右爬
		for (int i = 0; i < N; ++i)
		{
			double nd = (ih[i].position < 0.0 ? 0 : L) - ih[i].position;	// 离端点的距离
			if (nd > max_d + 1e-6)
			{
				max_d = nd;
				id = i;
				right = ih[i].position > 0.0;
			}
		}

		int count = 0;	// 该居民的前进路线上跟该居民反方向的个数
		if (right)
		{
			for (int i = id; i < N; ++i)
			{
				if (ih[i].position < 0.0)
				{
					++count;
				}
			}
			id += count;
		}
		else
		{
			for (int i = id; i >= 0; --i)
			{
				if (ih[i].position > 0.0)
				{
					++count;
				}
			}
			id -= count;
		}

		double result = max_d / V;
		cout << setw(13) << fixed << setprecision(2) << (int)(result * 100) / 100.0 << ' ' << ih[id].name << endl;	// 这里是截断，不是四舍五入
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

有个小插曲，我遇到了

Presentation Error指的是答案基本准确，只是格式不对，注意右对齐13个空格就行了。

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 2674 Linear world 题解 《挑战程序设计竞赛》