E_Log Jumping

• 2015 acm-icpc 예선
• Problem E Log Jumping

 

시작을 가장 큰 기둥을 양 끝의 기둥으로 선택하고
반복적으로 가장 큰 기둥을 2개씩 선택하여 이전의 기둥과 높이차를 구한다.
더 이상 선택할 기둥이 없을 때까지 선택한 두 기둥의 가장 큰 높이차를 기록한다.

using namespace std;

int main()
{
	int T;
	for (scanf("%d", &T); T--;)
	{
		vectorLog;
		int N;
		scanf("%d", &N);
		for (int i = 0; i < N; i++)
		{
			int L;
			scanf("%d", &L);
			Log.push_back(L);
		}
		
		sort(Log.begin(), Log.end());

		int des = Log.size() - 1;
		int Return = 0;
		int L, R;
		L = R = Log[des--];

		while (des > -1)
		{
			if (des > 0)
			{
				int BiggestA = Log[des--];
				int BiggestB = Log[des--];

				int nextGap = (L - BiggestA < R - BiggestB) ? R - BiggestB : L - BiggestA;
				if (Return < nextGap)
					Return = nextGap;
				L = BiggestA;
				R = BiggestB;
			}
			else
			{
				int Biggest = Log[des--];

				int nextGap = (L - Biggest < R - Biggest) ? R - Biggest : L - Biggest;
				if (Return < nextGap)
					Return = nextGap;
			}
		}
		printf("%d\n", Return);
	}
	return 0;
}