蹦蹦炸弹

应该又是一个模拟...模拟此生之敌.

首先考虑一个方向和不同速度的情况叭?

很容易想到,假如方向从右到左,那么我们按从左到右输入,考虑相邻两个,假如我右边那个速度小于左边那个,肯定是追不上的啦(这辈子都不可能追上).

从此我们可以得出,它们前面那些炸弹共存的条件就是速度递减,那么我假如突然来了一个速度大于它的咋办!肯定是把那个最前面那个速度最小的炸弹堆掉,一个方向的话,单调栈就可以做啦~

那么现在考虑两个方向,其实也差不多的.我们还是按从左往右考虑,方向为负我们用单调栈,方向为正我们用单调队列叭!队列嘛!肯定是单调递减的(对头到队尾),因为前面速度假如比我的大那我不是g了.

假设我现在在i的位子,那么就有两种情况嘛(其实就是两个方向罢了):

第一种情况就是我是从右往左的(负方向):

访问对头的位子,看它与栈顶位子哪个靠我更近,很显然喔,假如对头靠我近的话,咋两都没了.

假如栈顶靠我更近,就看我的大小和它的大小,假如我小于它的话,推进栈里,假如大于,咋两都没了.

第二种情况就是我是从左往右的(正方向):

这个就更简单了..因为我们还没遍历到前面,所以呢！就是判断它还对头的大小关系,假如小于对头

(读到这里你就会发现好像出现问题了叭,确实出问题了).

第一种情况有问题没?有问题！！！问题在于我无法保证后面的速度比我大的会不会超过我在我去前面的反方向位子的时候!!!!那么就改换个解法啦~

题解:考虑爆炸只会发生在相邻的两个炸弹,那么我们不妨把所有相邻的炸弹的信息放入set,然后每次找到爆炸时间尽可能短的,然后把它们删除,删除以后呢?肯定要把与它两相连的删除掉在set里,然后呢,把爆炸后的左右相连的点合并放入set.就做完了.貌似用链表做会出问题,,,实在想不通问题在哪,最后用set维护集合就行了.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const double eps=1e-3;
struct sb{
	double w;
	int ida,idb;
};
bool operator<(sb A,sb B)
{
	if(A.w==B.w)
	{
		if(A.ida==B.ida)	return A.idb<B.idb;
		else				return A.ida<B.ida;
	}
	else return A.w<B.w;
}

int l[N],r[N];//维护这个点左/右边下标是哪个点 
vector<int>res;
struct nm{
	double x,v;
	int id;
}b[N];

bool cmp(nm A,nm B)
{
	return A.x<B.x;
}

double Time(nm A,nm B)
{
	if(A.v>=0&&B.v<0||A.v>0&&B.v<=0)
	{
		return (B.x-A.x)/(A.v-B.v);
	}
	else if(A.v<=0&&B.v>=0)	return 1e9;
	else
	{
		if(A.v<0&&B.v<0&&A.v<=B.v)	return 1e9;
		if(A.v>0&&B.v>0&&A.v<=B.v)	return 1e9;
		double V=fabs(A.v-B.v);
        if(V<=eps)    return 1e9;
		return (B.x-A.x)/V;
	}
}

// void merge(int L,int R)
// {
// 	r[L]=R;
// 	l[R]=L;
// }


void run()
{
	//set 放三个元素一定是从左往右放
	int n;
	set<sb>s;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)	scanf("%lf",&b[i].x);
	for(int i=1;i<=n;i++)
	{
		scanf("%lf",&b[i].v);
		b[i].id=i;
	}
	sort(b+1,b+1+n,cmp);
	for(int i=1;i<=n;i++)
	{
		 if(i==1)
		 {
		 	l[b[i].id]=0;
		 	r[b[i].id]=b[i+1].id;
		 }
		 else if(i==n)
		 {
		 	l[b[i].id]=b[i-1].id;
		 	r[b[i].id]=n+1;
		 	if(fabs(Time(b[i-1],b[i])-1e9)<=eps)    continue;
		 	s.insert({Time(b[i-1],b[i]),b[i-1].id,b[i].id}); 
		 }
		 else
		 {
		 	l[b[i].id]=b[i-1].id;
		 	r[b[i].id]=b[i+1].id;
		 	if(fabs(Time(b[i-1],b[i])-1e9)<=eps)    continue;
		 	s.insert({Time(b[i-1],b[i]),b[i-1].id,b[i].id});
		 }
	}
    set<int>ans;
    for(int i=1;i<=n;i++)    ans.insert(i);
	while((int)s.size())
	{
		auto x=*s.begin();
		s.erase(x);
        if(ans.count(x.ida)&&ans.count(x.idb))    ans.erase(x.ida),ans.erase(x.idb);
        else									  continue;
		//cout<<x.ida<<' '<<x.idb<<'\n';
		auto it=ans.lower_bound(x.idb);
        if(it==ans.begin()||it==ans.end())    continue;
        int R=*it;--it;
        int L=*it;
        if(fabs(Time(b[L],b[R])-1e9)<=eps)    continue;
        //cout<<L<<' '<<R<<endl;
		s.insert({Time(b[L],b[R]),L,R});
        //merge(l[x.ida],r[x.idb]);
	}
	cout<<(int)ans.size()<<'\n';
	for(int x:ans)
	{
		printf("%d\n",x);
	}
}

int main()
{
	int T=1;
	//cin>>T;
	while(T--)
	{
		run();
	}
	return 0;
}
/*
5
1 3 5 7 9
-1 -2 -4 2 4

*/