贪心+思维
这一题我本来也是可以做的
经过一段时间的思考后我们可以发现,最先撞击的两个无人机一定是相邻的两个无人机
我们可以用一个优先队列维护所有的相邻的两点撞击的时间
然后贪心地取撞击时间小的点,然后更新
这个撞击时间是一个小数,在比较时有精度误差,因为精度误差我一直错
在涉及小数比较的时候,优先考虑是否可以进行ll比较,避免除法,转化为乘法
#include<iostream> #include<algorithm> #include<queue> using namespace std; typedef long long ll; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int max_n = 1e5+100; const double inf = 1e18; int n; pll ns[max_n]; int lft[max_n],rgt[max_n]; int tot=0; struct node { ll x,v; int l,r; node(ll xx,ll vv,int lf,int rr) { x=xx;v=vv;l=lf;r=rr; } bool operator<(const node& nn)const { bool ans; if (v<=0&&nn.v<=0)ans= l<nn.l; else if (v<=0)ans= false; else if (nn.v<=0)ans=true; else { ans=x*nn.v<nn.x*v; } return !ans; } }; bool used[max_n]; int main() { ios::sync_with_stdio(0); cin>>n; ++tot; for (int i=1;i<=n;++i) { cin>>ns[i].first>>ns[i].second; } for (int i=1;i<=n;++i)rgt[i]=i+1; for (int i=1;i<=n;++i)lft[i]=i-1; priority_queue<node> que; for (int i=2;i<=n;++i)que.push(node(ns[i].first-ns[i-1].first,ns[i-1].second-ns[i].second,i-1,i)); while (!que.empty()) { node nn = que.top(); que.pop(); if (nn.v<=0)break; int lt = nn.l,rt = nn.r; if (used[lt]||used[rt])continue; int L = lft[lt],R = rgt[rt]; used[lt]=used[rt]=1; if (L!=0&&R!=n+1) { que.push(node(ns[R].first-ns[L].first,ns[L].second-ns[R].second,L,R)); } rgt[L]=R; lft[R]=L; } int ans=0; for (int i=1;i<=n;++i) { if (!used[i])++ans; } cout<<ans<<endl; for (int i=1;i<=n;++i)if (!used[i])cout<<i<<" ";cout<<endl; }