[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;
}

留言

這個網誌中的熱門文章

[TIOJ] 1271. [IOI 2012] Scrivener 斯克里夫尼

[TIOJ] 1429. [APIO '12] 忍者調度問題

[Codeforces] 731D. 80-th Level Archeology