流浪地球(题目)

流浪地球
【题目描述】
2075年,不久太阳即将毁灭,太阳系将不适合人类生存。面对绝境,人类将开启“流浪地球”计划。

他们使用行星发动机转移地球。再转移过程中,本应该借助木星的引力为地球加速,但是因为计算错误被木星引力捕获。

现在有人提出燃烧木星。木星离地球n千米,行星发动机的火焰可以达到m千米高。但是m<n,所以点燃不了。

国际空间站现在有x艘飞船,所有飞船正好再地球和木星的最短路线上。

每艘飞船距离地球p[i]千米,爆炸范围为s[i]千米。

请问地球是否能继续以完整的形式存在?

【输入格式】
第二行为n,m,分别为木星与地球的距离和行星发动机的火焰最高高度。

第三行为x,即现有飞船。

第4~x+3行为p[i],s[i],即每艘飞船与地球间的距离和爆炸范围。

【输出格式】
如果可以点燃,输出”YES”,否则输出”NO”。

【样例输入】
100
70
8
10 20
70 10
20 10
50 40
62 1
13 2
55 5
66 70

【样例输出】
YES

【说明与数据范围】
n,m,p[i],s[i]都在int范围内
0<x<10000

解题思路

先求出行星发动机喷射范围内可以爆炸到最远的飞船。然后用这个飞船一层层递归下去。

找到飞船之后,继续找飞船爆炸范围内可以爆炸到最远的飞船……

直到找到能点燃木星的飞船为止,或者飞船全都用光,最后的飞船也没能点燃。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,x;
struct sp{
    int p;
    int s;
}ship[10000];
bool cmp(sp a,sp b){
    return a.p<b.p;
}
bool boom(int num){
//    cout<<num<<" "<<ship[num].p<<" "<<ship[num].s<<endl;
    if(ship[num].p+ship[num].s>=n){
        return true;
    }
    bool tf=false;
    int maxn=0;
    int choose=0;
    for(int i=num+1;i<x;i++){
        if(ship[i].p+ship[i].s>maxn&&ship[i].p<=ship[num].p+ship[num].s){
            maxn=ship[i].p+ship[i].s;
            choose=i;
        }
    }
    if(choose!=0){
        tf=boom(choose);
    }else{
        return false;
    }
    if(tf==true){
        return tf;
    } 
    if(num>=x-1){
        return false;
    }
    return tf;
}
int main(){
//    freopen("earth.txt","r",stdin);
//    freopen("earthout.txt","w",stdout);
    cin>>n>>m;
    cin>>x;
    for(int i=0;i<x;i++){
        cin>>ship[i].p>>ship[i].s;
    }
    sort(ship,ship+x,cmp);
    int could_a=0;
    int sh;
    for(int i=0;i<x;i++){
        if(ship[i].p<=m&&could_a<ship[i].p+ship[i].s){
            could_a=ship[i].p+ship[i].s;
            sh=i;
        }
    }
    bool yn=boom(sh);
    if(yn==true){
        cout<<"YES"<<endl;
        return 0;
    }else{
        cout<<"NO"<<endl;
    }
    return 0;
}
/*
100
70
8
10 20
70 10
20 10
50 40
62 1
13 2
55 5
66 70
*/ 

本题作者zk

本文链接:https://kaispace.com.cn/index.php/archives/290/

如果未注明出处,复制公开后需将注明本博客链接。
打赏作者