本文共 1317 字，大约阅读时间需要 4 分钟。

题目链接：

题目背景

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

题目描述

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

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

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

输入描述

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

输出描述

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

输入

5 10

6 8

2 100

7 3

1 10

2 5

输出

2

说明

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

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

备注

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

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

解题思路

如果自己就可以跳过去，就自己跳，否则，踩背上可能跳过去就存下来，如果一定不能到，当跳板。然后就排序、配对。如果跳板不够用，就舍弃一半当跳板。

Accepted Code:

#include 
   
    using namespace std;int sa[1000005], sb[1000005];bool cmp(int a, int b) {    return a > b;}int main() {    int n, s, x, y, ans, cnta, cntb;    ans = cnta = cntb = 0;    scanf("%d%d", &n, &s);    for (int i = 0; i < n; i++) {        scanf("%d%d", &x, &y);        if (x >= s)            ans++;        else if (x + y >= s)            sa[cnta++] = y;        else sb[cntb++] = x;    }    sort(sb, sb + cntb);    sort(sa, sa + cnta, cmp);    int i = 0, j = 0;    while (i < cnta && j < cntb) {        if (sa[i] + sb[j] >= s)            i++, j++, ans++;        else j++;    }    printf("%d\n", ans + (cnta - i) / 2);    return 0;}
   

转载地址：https://lzyws739307453.blog.csdn.net/article/details/92096251 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！