牛客小白月赛15A 斑羚飞渡

链接：https://ac.nowcoder.com/acm/contest/917/A

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 131072K，其他语言262144K
64bit IO Format: %lld

题目描述

题目背景

两个人之间只能有一个活着 ,这必然是我和你的战争——Harry Potter

题目描述

水宝宝在看完《斑羚飞渡》这本书后，突发奇想，想到了一个有趣的问题

现在峡谷的这边有n只斑羚，每只斑羚跳跃的最远距离为x[i],斑羚在别人的背上起跳的最远距离为y[i],峡谷的两岸的距离为s，问在最好情况下，有几只斑羚可以用别人的背当跳板跳到对岸，但由于斑羚的先天原因(主要是太肥)，只能把别人当跳板一次

注:本系列题不按难度排序哦

输入描述:

输入格式：

第一行n,s 接下来n行，每行2个整数代表x[i],y[i]

输出描述:

输出格式：

一行一个整数，表示有几只斑羚可以用别人的背当跳板跳到对岸

示例1

输入

复制

输出

复制

说明

第一组是第三只斑羚跳6的距离，第一只斑羚跳6的距离后从第三只的背上起跳，再跳8的距离后到达对岸

第二组是第五只跳2的距离，第二只跳2的距离后从第五只的背上起跳,跳100的距离到达对岸(假设对岸无限长，不可能跳出对岸)

备注:

对于100%的数据，n<=1000000;

对于所有数据，s<=1000000000; x[i],y[i]<=s; 不保证x[i]<y[i]

思路：
把羚羊分为三批，第一批是自己就能跳过去的，第二批是需要别人帮助能跳过去的，第三批是即使别人帮助了也跳不过去的（只能作为踏板或者被抛弃的，枯了）
不用说第一批了，跳过去就完事了。
第二批，需要第三批或者第二批自己内部来帮助，然后就排个序吧。
这时候考虑到第二批需要第三批羊帮助的底线是啥，起码第三批羊跳的范围满足x[j] >= s-y[i]吧,这样就能踩着他跳过去啦
比如说
2 13 
1 12 
4 3 
第一只就能踩着满足x[j] >= 13-12=1 的羊 跳过去。
这就是第二种情况：对当踏板的羊和要跳过去的羊分别排个序，从小到大取过去就行。
第三种情况也简单，第三批用不完的（工具人实锤了）直接被淘汰了。
第二批羊没了当踏板的羊，那就老老实实内部互相“帮助”吧，把剩下的除以二就行。
代码：

#include<bits/stdc++.h>

using namespace std;

#define LL long long

#define INF 2000000000

#define eps 1e-8

#define pi  3.141592653589793

const LL mod = 1e9+;

vector<pair<int,int> >v1,v2;

int main()

{

    int n,s;

    int sum1 = ,sum2 = ,sum3 = ;

    //sum1 自己本来就过得去的,sum2需要跟过不去的配合的,sum3两只能过得去的相互配合

    scanf("%d %d",&n,&s);

    for(int i =  ; i < n ; i++){

        int x,y;

        scanf("%d%d",&x,&y);

        if(x>=s)sum1++;

        else{

            pair<int,int>pii = make_pair(x,y);

            if(x+y >= s){

                v1.push_back(pii);

            }

            else{

                v2.push_back(pii);

            }

        }

    }

    sort(v1.begin(),v1.end());

    sort(v2.begin(),v2.end());

    if(!v2.empty()){

        for(int i =  ; i < v1.size() ; i++){

            int z = s - (v1[i].second);

            for(vector<pair<int,int> >::iterator it = v2.begin();it!=v2.end();it++){

                int x_j = it->first;

                if(x_j >= z){

                    sum2++;

                    v2.erase(it);

                    break;

                }

            }

            if(v2.empty()){

                break;

            }

        }

    }

    int last_v1 = v1.size() - sum2;

    if(last_v1 <= ){

        return printf("%d\n",sum1+sum2),;

    }//有机会跳过去的羊没剩余了

    else{

        sum3 = last_v1/;

        return printf("%d\n",sum1+sum2+sum3),;

    }

}

巴特西

牛客小白月赛15A 斑羚飞渡

题目描述

题目背景

题目描述

输入描述:

输出描述:

输入

输出

说明

备注:

最新文章

热门文章