P8593 「KDOI-02」一个弹的投 题解

· · 题解

其实除了提示中给的平抛运动落点公式本题和物理基本没关系

首先有一个结论，只有 y 坐标相同相同的导弹会相撞。为什么呢？因为所有导弹都是从同一时刻开始降落，而重力是相同的，所以两颗初始 y 坐标不同的导弹在任意一颗接触到 x 轴前相对高度始终不变。也就是说，他们的 y 坐标始终不同，自然就不会相撞。

那么，我们可以对每一个 y 坐标上的导弹分别求解。设导弹的落点为 d，我们发现，对于两颗 y 坐标相同的导弹 i,j，若 x_i < x_j，有且仅有在 d_i\ge d_j 的情况会相撞，因为两颗导弹一定会有交点。那就非常简单了，我们只需要将每一个 y 坐标的所有导弹，对 x 坐标排序，然后每一个导弹分别针对落点 d 求出有关的逆序对个数，也就是对每个 i 求出满足 x_i < x_j\land d_i\ge d_j\lor x_i < x_j\land d_i\le d_j\quad(y_i=y_j) 的 j 的个数，就是他的威力了。

求出所有导弹的威力后，就是一个非常简单的贪心题了。设导弹的威力为 v，则启动第 i 台反制武器可以减少 f_i=\min(a_i,v_i) 爆炸威力值，取最大的 m 个 f_i 是最优的。用导弹爆炸威力的总和减去最大的 m 个 f_i 就是最小的导弹造成的爆炸威力值总和。时间复杂度 O(n\log n)。

#include<bits/stdc++.h>
using namespace std;
const int N=500001;
const double g=9.8;
int n,m,x,y,v,id,s,T[N],V[N],a,f[N];
long long sum;
double d[N];
map<int,int>mp;
map<int,int>::iterator it;
struct daodan{
    int id,x;
    double d;
};
bool cmp(daodan a,daodan b){
    return a.x>b.x;
}
bool Cmp(int a,int b){
    return a>b;
}
vector<daodan>t[N];
void add(int x){
    for(;x<=s;x+=x&-x)T[x]++;
}
int get(int x){
    int ans=0; 
    for(;x;x-=x&-x)ans+=T[x];
    return ans;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>x>>y>>v;
        if(!mp[y])mp[y]=++id;
        t[mp[y]].push_back({i,x,x+v*sqrt(2*y/g)});//对于每一个 y 坐标上的导弹分别求解 
    }
    for(auto it:mp){
        x=it.second,sort(t[x].begin(),t[x].end(),cmp),s=t[x].size();
        for(int i=0;i<s;i++)d[i]=t[x][i].d;
        sort(d,d+s);//树状数组求逆序对，前后都要求一次 
        for(int i=1;i<=s;i++)T[i]=0; 
        for(int i=0;i<s;i++){
            t[x][i].d=upper_bound(d,d+s,t[x][i].d)-d;//离散化
            V[t[x][i].id]+=get(t[x][i].d);
            add(t[x][i].d);
        }
        for(int i=1;i<=s;i++)T[i]=0;
        for(int i=s-1;i>=0;i--){
            V[t[x][i].id]+=s-1-i-get(t[x][i].d-1);
            add(t[x][i].d);
        }
    }
    for(int i=1;i<=n;i++)cin>>a,sum+=V[i],f[i]=min(a,V[i]);//贪心部分 
    sort(f+1,f+1+n,Cmp);
    for(int i=1;i<=m;i++)sum-=f[i];
    cout<<sum;
}