uva-10714-贪心

题意:有一条杆，长度为L，上面很几只蚂蚁,蚂蚁的朝向未知,爬速1cm/s,在爬行过程中,蚂蚁相撞了就往反方向爬,问,杆上没有蚂蚁至少要多久,至多要多久

解题思路:

蚂蚁1和蚂蚁2相撞，我们只要交换一下1和2的编号就可以,相当于没碰撞.

#include "pch.h"

#include <string>

#include<iostream>

#include<map>

#include<memory.h>

#include<vector>

#include<algorithm>

#include<queue>

#include<vector>

namespace cc

{

	using std::cout;

	using std::endl;

	using std::cin;

	using std::map;

	using std::vector;

	using std::string;

	using std::sort;

	using std::priority_queue;

	using std::greater;

	using std::vector;

	constexpr int N = 5000;

	//priority_queue<int,vector<int>, greater<int> >q;

	void solve()

	{

		int n;

		cin >> n;

		while (n--)

		{

			auto MAX = INT32_MIN;

			auto MIN = INT32_MAX;

			int m1, m2, m;

			int L;

			cin >> L;

			if (L % 2 == 0)

				m1 = m2 = L / 2;

			else

			{

				m1 = L / 2;

				m2 = (L + 1) / 2;

			}

			int total, k;

			cin >> total;

			for (int i = 0;i < total;++i)

			{

				cin >> k;

				//max

				if (k > MAX)

					MAX = k;

				if (L - k > MAX)

					MAX = L - k;

				//min,离中点最近的点,

				if (k <= m1)

				{

					if (MIN > m1 - k)

					{

						MIN = m1 - k;

						m = k;

					}

				}

				else if (k >= m2)

				{

					if (MIN > k - m2)

					{

						MIN = k - m2;

						m = k;

					}

				}

			}

			m = m < L - m ? m : L - m;

			cout << m << " " << MAX << endl;

		}

	}

};

int main()

{

#ifndef ONLINE_JUDGE

	freopen("d://1.text", "r", stdin);

#endif // !ONLINE_JUDGE

	cc::solve();

	return 0;

}