P8593 「KDOI-02」一个弹的投 题解
|
老官童鞋gogo
|
123
|
0
|
程序设计,题解
|

2356 字
|
24 分钟

P8593 「KDOI-02」一个弹的投

题目传送门

题目背景

  • 前置芝士：平抛运动 （看到这个如果不想做可以直接开下一题）

「这群该死的外星人，肯定是来抢夺新矿资源的！」

「这导弹什么鬼啊，研究不明白。」

无数的水滴型武器从苍穹之外落下，猛击着无知的生命。

题目描述

经研究，该武器的运作方式是这样的。其中设重力方向为 $y$ 轴负半轴，$x$ 轴为地面，速度向右为正向左为负。

  • 每颗导弹在 $(x_i,y_i)$ 的地方投放并悬浮，初始速度设置为 $v_i$。
  • 所有导弹投放完成后，于同一时刻开始照初始速度做平抛运动。其中 $g=9.8$。
  • 每颗导弹与另一颗导弹碰撞时，不会改变原来的路线，并且将爆破威力 $p_i$ 增加 $1$，所有导弹初始时 $p_i=0$，在接触到 $x$ 轴时碰撞也增加威力。
  • 当武器落到 $x$ 轴时，会对落点造成 $p_i$ 点杀伤力。

地面指挥部提前预测了导弹的落点，并部署了反制武器。第 $i$ 台武器能将第 $i$ 枚导弹在降落至地面后的威力值减少 $a_i$（至多减少到 $0$）。但是，由于技术限制，只能启动其中 $m$ 台反制武器。地面指挥官想知道，导弹造成的爆炸威力值总和最小为多少。

输入格式

从标准输入中读入数据。

输入一共包含 $n+2$ 行。

第 $1$ 行输入两个正整数 $n,m$。

第 $2$ 行到第 $n+1$ 行每行包含三个整数 $x_i,y_i,v_i$，表示第 $i$ 颗导弹的起点坐标和水平速度。

第 $n+2$ 行包含 $n$ 个非负整数 $a_1,a_2,\cdots,a_n$，含义见题目描述。

输出格式

输出到标准输出。

输出一行一个非负整数，表示答案。

样例 #1

样例输入 #1

3 0
1 1 -2
1 2 -1
1 3 1
1 1 1

样例输出 #1

0

样例 #2

样例输入 #2

4 1
-3 3 0
1 3 1
4 3 -4
-9 3 -7
1 3 2 3

样例输出 #2

1

提示

【样例解释】

  • 样例 1 解释： 每颗导弹的爆炸威力值都是 $0$。

  • 样例 2 解释： 四枚导弹的爆炸威力值分别是 $0,1,1,0$，启动第 $2$ 或第 $3$ 台反制武器，最后爆炸威力值的和为 $1$。

【数据范围】

对于 $100%$ 的数据，$1\le n\le5\times10^5$，$0\le a_i,m\le n$，$0\le |x_i|,y_i\le10^9$，$0\le |v_i|\le10^6$。

保证所有导弹起始坐标不相等。

测试点编号$n\le$特殊性质
$1\sim6$$5000$无
$7\sim10$$12000$无
$11\sim12$$10^5$有
$13\sim16$$10^5$无
$17\sim20$$5\times10^5$无
特殊性质：保证所有 $y_i$ 均相同。

心得

逃课打的这次模拟赛

考试过程中第一题很快就想出来了，不过写代码、调试细节足足用了将近两个小时。自己的代码能力还是太弱了。

第一题做完之后很激动，然后二三四题都不会了……

题解

模块一：读入

没有什么好说的，看代码吧。

read(n,m); //使用快读
for(int i=1;i<=n;i++){
    read(mis[i].x,mis[i].y,mis[i].v); //mis[i]结构体数组用来记录编号为i的导弹信息
    mis[i].i=i; //导弹编号
    t=sqrt((2.0*mis[i].y)/9.8); //求运动时间（见公式推导)
    mis[i].to=(double)mis[i].x+(double)mis[i].v*t; //求最终落点（见公式推导）
}

模块二：探究两导弹相撞条件

如果你学过《人教版高中物理必修二》的抛体运动一章的话，可以跳过下面的公式推导。

已知物体做自由落体（初速度为 $0$ )的高度 $h$ 与时间 $t$ 、重力加速度 $g$ 的关系为：$$h=\frac{1}{2}gt^2$$

因为所有导弹在同一时刻发射，并设第 $i$ 颗导弹的高度为 $y_i$ ，初速度为 $v_i$ ，那么可以根据公式得到导弹下落时间 $t_i$ ：

$$\begin{aligned} & y_i=\frac{1}{2}gt_i^2 \\ \Leftrightarrow & t_i=\sqrt{\frac{2y_i}{g}}\end{aligned}$$

由此得到水平方向上位移 $\Delta x_i$ ：

$$\begin{aligned} \Delta x_i & =v_it_i \\ & =v_i\sqrt{\frac{2y_i}{g}} \end{aligned}$$

再加上原来的横坐标就可以得到题目中所给的公式了。

根据推导公式的过程不难发现，在相同的时间内，所有导弹下落的高度是相同的，与水平初速度和质量没有任何关系。有的人可能认为它们下落的轨迹存在交点就会相撞，这是不对的，因为相撞需要满足两个条件：

  1. 它们所在的位置为同一点。
  2. 它们在同一时间到达同一点。

又因为所有的导弹同时开始降落，所以对于两个导弹，只有它们初始位置在同一高度上，它们才有可能相撞。

在做题的时候，我们只需要将所有导弹按照纵坐标排序，将纵坐标相同的导弹放在一起讨论是否会相撞即可。

bool cmp1(Node1 x,Node1 y){
    if(x.y!=y.y)
        return x.y<y.y; //先排纵坐标
    else if(x.x==y.x)
        return x.to<y.to; //横坐标相同，将落点靠右的放在右边（见文末细节部分）
    else
        return x.x<y.x; //横坐标排序
}
sort(mis+1,mis+1+n,cmp1); //导弹按照纵坐标排序
for(int i=1;i<=n;i++){
    bot[++nxt].num=mis[i].i; //bot[]结构体数组中存储着纵坐标相同的导弹信息。
    bot[nxt].to=mis[i].to;
    if(mis[i].y!=mis[i+1].y){ 
        get_pair(1,nxt); //求解函数
        nxt=0;
        continue;
    }
}

模块三：判断两导弹是否会相撞

由平抛运动特点及推导公式可知，平抛运动中两个导弹水平运动方向是确定的，也就是说不会走着走着调个头，所以一枚导弹运动横坐标左右断点为初始横坐标和落地点的横坐标。

根据模块二，我们通过导弹的初始位置计算出了导弹的落点位置，假设导弹 $i$ 和 $j$ ，它们的初始位置满足关系 $x_i \le x_j$，并且落点位置满足 $to_i \ge to_j$ ，说明两个导弹在发射过程中相撞了。图示：

平抛碰撞判定

所以计算每个导弹到达地面时的威力值就是计算满足上述关系的含有该导弹编号的有序数对 $(i,j)$ 有多少（你当然可以暴力枚举求解）。

是不是很像逆序对呢？

模块四：归并排序求导弹威力值

树状数组的求法不是不可以，不过这里我还是使用了归并排序。

前提是我们得到了该纵坐标下的所有导弹，并对其横坐标排序，要求是稳定排序，防止特殊情况发生（见细节部分）。利用求逆序对的思想，以导弹初始的横坐标顺序做编号，以落点位置横坐标作为值进行归并排序。将归并排序的框架写好，每当我们交换了一次顺序，说明这颗导弹发生了一次碰撞，具体实现看代码。

void get_pair(int l,int r){ //按照落点
    int mid=(l+r)>>1;
    if(l>=r)    return;
    get_pair(l,mid);
    get_pair(mid+1,r); //递归求解
    int p1=l,p2=mid+1,p=l,cnt=0;
    while(p1<=mid&&p2<=r){
        if(bot[p1].to<bot[p2].to){
            f[bot[p1].num]+=cnt; //cnt作用见下，f[]数组用于记录导弹威力值
            temp[p++]=bot[p1++];
        }
        else{
            cnt++; //因为在归并排序中左半部分和右半部分分别都是有序的，右半部分的导弹与左半部分的一个导弹相撞，那么它会与相撞导弹的右边所有导弹都相撞，这里使用了cnt来维护后面导弹的相撞次数。
            f[bot[p2].num]+=mid-p1+1;
            temp[p++]=bot[p2++];
        }
    }
    while(p1<=mid){
        f[bot[p1].num]+=cnt;
        temp[p++]=bot[p1++];
    }
    while(p2<=r)
        temp[p++]=bot[p2++];
    for(int i=l;i<=r;i++){
        bot[i]=temp[i];
    }
    return;
}

模块五：整理答案

最后计算出使用每个反制武器最少可以减去多少威力值，并进行排序，贪心使用最大的 $m$ 个反制武器并计算最终答案即可。

bool cmp2(Node1 x,Node1 y){
    return x.i<y.i;
}
bool cmp3(Node3 x,Node3 y){
    return x.num>y.num;
}
sort(mis+1,mis+1+n,cmp2); //整理导弹序号
for(int i=1;i<=n;i++){
    read(a[i]);
    if(a[i]>f[i]){ //计算使用第i个反制武器的价值
        val[i].num=f[i];
        val[i].i=i;
    }
    else{
        val[i].num=a[i];
        val[i].i=i;
    }
}
sort(val+1,val+1+n,cmp3); //对价值进行排序贪心
for(int i=1;i<=m;i++)
    vis[val[i].i]=1;
for(int i=1;i<=n;i++){
    if(vis[i]==1)
        if(a[i]>f[i])
            ans+=0;
    else
        ans+=f[i]-a[i];
    else
        ans+=f[i];
}

细节部分

  1. 比赛过程中，管理员对本题进行的题意补充：在接触到 $x$ 轴时碰撞也增加威力（还有一句是初始位置相同不算碰撞，后来又删去了，这就是我为什么在排序的时候要把落点位置靠右的的点排序在右边，防止在抛出时判断为一次有效碰撞），所以在书写代码判断碰撞的时候要带上等于号。
  2. 分析清楚归并排序时应该如何处理导弹威力值。
  3. 搞清楚反制武器是怎么去贪心的
  4. 排序前后编号一定要一一对应，灵活使用结构体。

完整代码

完整代码中包括各种加速，研究时可以忽略。

#include<bits/stdc++.h>
using namespace std;
namespace Fast{
#define uint unsigned int
#define ll long long
#define ull unsigned long long
#define int128 __int128
#define uint128 unsigned __int128
#define Ld long double
#define space putchar(' ')
#define enter putchar('\n')
#define PI acos(-1)
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define fi first
#define se second
#define pr(x) cerr<<#x<<"="<<(x)<<"\n"
#define inf 1000000000
#define INF 1000000000000000000
#define N 1010
#define M 500010
    template<class T>inline bool read(T &x){
        x=0;char c=getchar();bool f=0;
        while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
        while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
        if(f)x=-x;
        return true;
    }
    template<typename T>inline void print(T x){
        int s[65],top=0;
        if(x<0)putchar('-'),x=~x+1;
        while(x)s[++top]=x%10,x/=10;
        if(!top)s[++top]=0;
        while(top)putchar(s[top--]+'0');
    }
    template<class T>inline bool readd(T &x){
        ll X=0;double y=1.0;char c=getchar();bool f=0;
        while(!isdigit(c)){if(c==EOF)return false;f^=c=='-',c=getchar();}
        while(isdigit(c))X=(X<<3)+(X<<1)+(c^48),c=getchar();
        x=X;
        if(c!='.'&&c!='E'&&c!='e'){if(f)x=-x;return true;}
        if(c=='.'){c=getchar();while(isdigit(c))x+=(y/=10)*(c^48),c=getchar();}
        if(f)x=-x;
        X=0;f=0;
        if(c=='E'||c=='e'){
            c=getchar();
            while(!isdigit(c)){if(c==EOF)return true;f^=c=='-',c=getchar();}
            while(isdigit(c))X=(X<<3)+(X<<1)+(c^48),c=getchar();
        }
        if(f)for(ll i=1;i<=X;i++)x/=10;
        else for(ll i=1;i<=X;i++)x*=10;
        return true;
    }
    template<class T>inline void printd(T x,int y){
        static ll mul[]={1};
        for(ll i=1;i<=18;i++)
            mul[i]=(mul[i-1]<<3)+(mul[i-1]<<1);
        if(x<-1e-12)putchar('-'),x=-x;
        x*=mul[y];
        ll x1=(ll)round(x),x2=x1/mul[y],x3=x1-x2*mul[y];
        print(x2);
        if(y>0){
            putchar('.');
            for(ll i=1;i<y&&x3*mul[i]<mul[y];putchar('0'),i++);
            print(x3);
        }
    }
    template<class T>inline bool readc(T &x){
        char c=getchar();
        while(c==' '||c=='\n'||c=='\r'||c=='\t')c=getchar();
        if(c==EOF)return false;
        x=c;
        return true;
    }
    template<class T>inline void printc(T x){putchar(x);}
    template<class T>inline bool readcc(T *x){
        char c=getchar();
        while(c==' '||c=='\n'||c=='\r'||c=='\t')c=getchar();
        if(c==EOF)return false;
        while(c!=' '&&c!='\n'&&c!='\r'&&c!='\t'&&c!=EOF)*x++=c,c=getchar();
        *x=0;
        return true;
    }
    template<class T>inline void printcc(T *x){while(*x)putchar(*x++);}
    template<class T>inline bool reads(T &x){
        x="";char c=getchar();
        while(c==' '||c=='\n'||c=='\r'||c=='\t')c=getchar();
        if(c==EOF)return false;
        while(c!=' '&&c!='\n'&&c!='\r'&&c!='\t'&&c!=EOF)x+=c,c=getchar();
        return true;
    }
    template<class T>inline void prints(T x){for(ll i=0;x[i]!='\0';i++)putchar(x[i]);}
    template<class T,class ...S>inline bool read(T &x,S &...y){return read(x)&&read(y...);}
    template<class T,class ...S>inline bool readd(T &x,S &...y){return readd(x)&&readd(y...);}
    template<class T,class ...S>inline bool readc(T &x,S &...y){return readc(x)&&readc(y...);}
    template<class T,class ...S>inline bool readcc(T *x,S *...y){return readcc(x)&&readcc(y...);}
    template<class T,class ...S>inline bool reads(T &x,S &...y){return reads(x)&&reads(y...);}
    template<class T,class ...S>inline void print(T x,S ...y){print(x),putchar(' '),print(y...);}
    template<class T,class ...S>inline void printd(T x,S ...y){printd(x),putchar(' '),printd(y...);}
    template<class T,class ...S>inline void printc(T x,S ...y){printc(x),putchar(' '),printc(y...);}
    template<class T,class ...S>inline void printcc(T *x,S *...y){printcc(x),putchar('\n'),printcc(y...);}
    template<class T,class ...S>inline void prints(T x,S ...y){prints(x),putchar('\n'),prints(y...);}
    const double eps=1e-7;
    template<typename T>inline T Abs(T x){return x>0?x:-x;}
    template<typename T>inline T Max(T x,T y){return x>y?x:y;}
    template<typename T>inline T Min(T x,T y){return x<y?x:y;}
    template<typename T>inline T Fabs(T x){return x>eps?x:-x;}
    template<typename T>inline T Fmax(T x,T y){return x-y>eps?x:y;}
    template<typename T>inline T Fmin(T x,T y){return x-y<eps?x:y;}
}
using namespace Fast;
struct Node1{
    ll x,y,v,p,i;
    double to;
}mis[M];
struct Node2{
    ll num;
    double to;
}bot[M],temp[M];
struct Node3{
    ll i,num;
}val[M];
ll n,m,nxt;
ull ans,f[M],a[M];
bool vis[M];
double t;
bool cmp1(Node1 x,Node1 y){
    if(x.y!=y.y)
        return x.y<y.y;
    else if(x.x==y.x)
        return x.to<y.to;
    else
        return x.x<y.x;
}
bool cmp2(Node1 x,Node1 y){
    return x.i<y.i;
}
bool cmp3(Node3 x,Node3 y){
    return x.num>y.num;
}
void get_pair(int l,int r){
    int mid=(l+r)>>1;
    if(l>=r)    return;
    get_pair(l,mid);
    get_pair(mid+1,r);
    int p1=l,p2=mid+1,p=l,cnt=0;
    while(p1<=mid&&p2<=r){
        if(bot[p1].to<bot[p2].to){
            f[bot[p1].num]+=cnt;
            temp[p++]=bot[p1++];
        }
        else{
            cnt++;
            f[bot[p2].num]+=mid-p1+1;
            temp[p++]=bot[p2++];
        }
    }
    while(p1<=mid){
        f[bot[p1].num]+=cnt;
        temp[p++]=bot[p1++];
    }
    while(p2<=r)
        temp[p++]=bot[p2++];
    for(int i=l;i<=r;i++){
        bot[i]=temp[i];
    }
    return;
}
int main(){
    read(n,m);
    for(int i=1;i<=n;i++){
        read(mis[i].x,mis[i].y,mis[i].v);
        mis[i].i=i;
        t=sqrt((2.0*mis[i].y)/9.8);
        mis[i].to=(double)mis[i].x+(double)mis[i].v*t;
    }
    sort(mis+1,mis+1+n,cmp1);
    for(int i=1;i<=n;i++){
        bot[++nxt].num=mis[i].i;
        bot[nxt].to=mis[i].to;
        if(mis[i].y!=mis[i+1].y){
            get_pair(1,nxt);
            nxt=0;
            continue;
        }
    }
    sort(mis+1,mis+1+n,cmp2);
    for(int i=1;i<=n;i++){
        read(a[i]);
        if(a[i]>f[i]){
            val[i].num=f[i];
            val[i].i=i;
        }
        else{
            val[i].num=a[i];
            val[i].i=i;
        }
    }
    sort(val+1,val+1+n,cmp3);
    for(int i=1;i<=m;i++)
        vis[val[i].i]=1;
    for(int i=1;i<=n;i++){
        if(vis[i]==1)
            if(a[i]>f[i])
                ans+=0;
            else
                ans+=f[i]-a[i];
        else
            ans+=f[i];
    }
    print(ans);
    return 0;
}

有问题是难免的，请不要客气地在评论区指出。

文章标题：P8593 「KDOI-02」一个弹的投 题解
文章链接：https://www.laoguantx.top/p8593-%e3%80%8ckdoi-02%e3%80%8d%e4%b8%80%e4%b8%aa%e5%bc%b9%e7%9a%84%e6%8a%95-%e9%a2%98%e8%a7%a3.html
文章内容仅供参考，其中可能会有部分内容参考、引用其他网站，转发请务必标注作者为 “老官童鞋gogo” ，原文链接为 https://www.laoguantx.top/p8593-%e3%80%8ckdoi-02%e3%80%8d%e4%b8%80%e4%b8%aa%e5%bc%b9%e7%9a%84%e6%8a%95-%e9%a2%98%e8%a7%a3.html 。
归并排序物理
暂无评论

发送评论 编辑评论 


				

			

						

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
						

					

				

				

					

						

							

								
							

							
							
													

					

				

			

			
			

				

					
				

			

				

											

							
							
						

																

							
							
						

																

							
							
						

										
					
											
						

	

		
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
（╯‵□′）╯︵┴─┴
￣﹃￣
(/ω＼)
∠( ᐛ 」∠)＿
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ｀)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ(￣∇￣o)
ヾ(´･ ･｀｡)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò｡)
Σ(っ °Д °;)っ
( ,,´･ω･)ﾉ"(´っω･｀｡)
╮(╯▽╰)╭
o(*////▽////*)q
＞﹏＜
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
	

	

		
颜文字
Emoji
小恐龙
花!
	


									

			

			
			
		

	






上一篇
下一篇 

                    

                    
			        推荐文章
		            

		            

							
扫描线

							
							

							
P3956 [NOIP2017 普及组] 棋盘 题解

							
							

							
OI常用数列

							
							

							
最小生成树

							
							

							
线性动态规划