[TIOJ] 1948. 小向的試煉 2-1：洞穴(Cave)

題目連結:http://tioj.infor.org/problems/1948

---

首先可以發現反彈其實就是兩個人交換工作而已，所以其實時間不會改變，再來就是若由左到右有abc三人，則a或c一定比b早出來，甚至ac都出來了，b才出來，由這兩個性質可以$O(1)$得出是誰先出來的，只要先對位置排序，然後從左往右掃紀錄往左的人，並從右往左掃，紀錄往右的人，然後每次比他們兩個最外面的那個人的距離如果右邊比較小，則讓整個隊列右邊的人出去(代表是他幫忙做完事情)，反之亦然，直到整串隊伍剩下一個人為止，它就是最晚出來的那個

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
#define N 1000000
#define xianL 0
#define xianR 1

struct dg{
	lld pos,xian,id;
};
dg dragon[N + 5];
bool cmp(dg a,dg b){return a.pos<b.pos;}

int main(){
	lld n,l;
	scanf("%lld%lld",&n,&l);
	for(int i=0;i<n;i++){
		scanf("%lld%lld",&dragon[i].pos,&dragon[i].xian);
		dragon[i].id=i;
	}
	sort(dragon,dragon+n,cmp);
	queue<lld> ll,rr;
	for(int i=0;i<n;i++)
		if(dragon[i].xian==xianL)ll.push(dragon[i].pos);
	for(int i=n-1;i>=0;i--)
		if(dragon[i].xian==xianR)rr.push(l-dragon[i].pos);
	int dgL=0,dgR=n-1;
	while(dgR!=dgL){
		if(ll.empty()){
			dgR--;
			rr.pop();
		}else if(rr.empty()){
			dgL++;
			ll.pop();
		}else{
			if(rr.front()<ll.front()){
				dgR--;
				rr.pop();
			}else{
				dgL++;
				ll.pop();
			}
		}
	}
	printf("%lld",dragon[dgR].id);
	return 0;
}