sicily 1063之迭代器

讲的是一个薪水和身高的问题。如果A的薪水和身高都比B高，那么A就是B的上司；进一步地，如果A是比B的薪水高的人中薪水最少的，并且A的身高至少和B一样高，那么A就是B的直接上司。具体的题目在这里题目

乍看一眼，觉得这道题要用树，后来想想用树又解决不了。因为，你不知道这棵树有多少个分叉。当然，如果你愿意在每个node里面添加一个很大规模的指针数组（如：30000个，题目说最多只会有30000个节点）也可以。

因此，我放弃了树来写这道题。转而，我用的是vector，因为我不想预先开一个大的空间（虽然vector源码里面也会这样做）。既然用了vector，那一定会用到排序，可以考虑现成的c++快排函数sort。这样一想，思路就会很清晰。既然用排序，一定要有比较函数。所以，下一步考虑的就是把那个作为主要的比较参数，salary还是height。

在这里，我其实是犯了错误的。之前我用height作为参数，提交几次总是通不过之后，自己琢磨测试数据，发现height不是题目意思里的主要参数，salary才是主要的参数。因此，如果你已经决定把salary作为主要参数。那么，下一步就可以考虑一下怎么找出boss和subordinate。

题目就讲到这里，我不喜欢把所有的思路都说出来，因为每次我都会把源码贴出来，不懂得可以看源码，我的注释也很详尽。

现在，进入到这篇博客的重点——STL里的iterator和reverse_iterator。

众所周知，这两个东西是用在STL里container的，是用来遍历的，是双向的迭代器。那么，begin（），end（），rbegin（），rend（）都是指什么呢？好，我们看个图，就会一目了然

如上图所示，8,7,6为一个vector，上面表示iterator的方向，下面表示reverse_iterator的方向。其中，end（）和rbegin（）的值是无效的，begin（）和rend（）表示的是vector的头。然后，现在令两个迭代器iter为正迭代器，riter为反迭代器。那么，假如iter的位置在上图上半部分中左边第二个向下箭头的位置，riter为相对的位置。那么，*iter的值是7，而*riter为8。具体原因，应该可以用那两个向左和向右的箭头来解释吧。总之，以后大家用的时候，可以留心一点。

下面是1063我自己的源码，仅供参考

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

struct Worker
{
	int m_employee_id;
	int m_salary;
	int m_height;

	Worker(int id, int salary, int height)
	{
		m_employee_id = id;
		m_salary = salary;
		m_height = height;
	}
};

vector<Worker> worker;

bool comp(Worker w1, Worker w2)
{
	if (w1.m_salary > w2.m_salary)
		return true;
	return false;
}

int main()
{
	int n, m, q;
	cin >> n;
	int id, salary, height;
	Worker *w = NULL;
	int boss, subordinate;
	bool isExist = false;
	while (n--)
	{
		cin >> m >> q;
		while (m--)
		{
			cin >> id >> salary >> height;
			w = new Worker(id, salary, height);
			worker.push_back(*w);
		}

		sort(worker.begin(), worker.end(), comp);

		while (q--)
		{
			cin >> id;

			isExist = false;
			vector<Worker>::iterator iter = worker.begin();
			vector<Worker>::reverse_iterator riter = worker.rend();/* record the position to finding boss,
																	because boss's position is former than subordinate
																	*/

			for (; iter != worker.end(); iter++, riter--)
			{
				if ((*iter).m_employee_id == id)
				{
					boss = 0;
					subordinate = 0;
					isExist = true;
					
					//look for subordinate
					for (vector<Worker>::iterator next = iter; next != worker.end(); next++)
					{
						if ((*next).m_height <= (*iter).m_height)/*because of recording itself, 
																so there is a subordinate - 1 in following cout statement
																*/
							subordinate++;
						else
							break;
					}

					//look for boss
					for (vector<Worker>::reverse_iterator prev = riter; prev != (worker.rend()); prev++)
					{
						if (((*prev).m_height - (*iter).m_height) >= 0)//not record itself, see this blog
						{
							boss = (*prev).m_employee_id;
							break;
						}
					}

					cout << boss << " " << subordinate-1 << endl;
					break;
				}
			}
			if (isExist == false)
				cout << "0 0" << endl;
		}
		worker.clear();
	}
	system("pause");
	return 0;
}