求助
考虑爆炸只会发生在相邻的两个炸弹,那么我们不妨把所有相邻的炸弹的信息放入set,然后每次找到爆炸时间尽可能短的,然后把它们删除,删除以后呢?肯定要把与它两相连的删除掉在set里,然后呢,把爆炸后的左右相连的点合并放入set.就做完了.左右相连用链表维护.
不知道wa在哪里了...求大佬看看
#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];//维护这个点左/右边下标是哪个点
bool ans[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;
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;
s.insert({Time(b[i-1],b[i]),b[i-1].id,b[i].id});
}
}
for(int i=1;i<=n/2;i++)
{
auto x=*s.begin();
if(fabs(x.w-1e9)<=eps) break;
s.erase(x);
if(l[x.ida]!=0) s.erase({Time(b[l[x.ida]],b[x.ida]),l[x.ida],x.ida});
if(r[x.idb]!=n+1) s.erase({Time(b[x.idb],b[r[x.idb]]),x.idb,r[x.idb]});
if(l[x.ida]!=0&&r[x.idb]!=n+1)
{
s.insert({Time(b[l[x.ida]],b[r[x.idb]]),l[x.ida],r[x.idb]});
}
merge(l[x.ida],r[x.idb]);
}
for(auto x:s)
{
if(!ans[x.ida]) ans[x.ida]=true,res.push_back(x.ida);
if(!ans[x.idb]) ans[x.idb]=true,res.push_back(x.idb);
}
printf("%d\n",(int)res.size());
sort(res.begin(),res.end());
for(int x:res)
{
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
*/ 
