自动搬运

查看原文

来自洛谷，原作者为

	Ray1 如愿

搬运于2025-08-24 22:40:30，当前版本为作者最后更新于2022-10-24 08:24:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

首先有一个结论，只有 $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;
}