放牧代码和思想
专注自然语言处理、机器学习算法

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//////////////////////////////////

有个小插曲,我遇到了

12896670 hankcs 2674 Presentation Error C++ 1799B 2014-05-20 00:25:13

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

12896681 hankcs 2674 Accepted 1500K 1313MS C++ 1792B 2014-05-20 00:30:17

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

分享到:更多 ()

评论 2

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #1

    博主用的什么编译器啊?

    传道者2年前 (2015-10-10)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机