【Horn Studio】编程专栏： 抢气球  解题思路

题目

题目描述

A教室的墙上挂满了五颜六色的气球，小朋友们都非常喜欢。刚一下课，小朋友们就打算去抢这些气球。每个气球在墙上都有一定的高度，只有当小朋友跳起来时，手能够到的高度大于等于气球的高度，小朋友才能摘到这个气球。
为了公平起见，老师让跳的低的小朋友先摘，跳的高的小朋友后摘。小朋友都很贪心，每个小朋友在摘气球的时候都会把自己能摘的气球都摘掉。很巧的是，小朋友们跳起来手能够着的高度都不一样，这样就不会有跳起来后高度相同的小朋友之间发生争执了。

输入

第一行输入两个空格分隔的整数n,m，其中n表示小朋友的数量，m表示墙上气球的数量。
第二行输入n个正整数（每两个整数之间用空格隔开），第i个数为 aiai，表示第i个小朋友跳起来手能够着的高度。
第三行输入m个正整数（每两个整数之间用空格隔开），第i个数为 hihi，表示第i个气球的高度
0<n、m≤100000，0<ai、hi≤1090<n、m≤100000，0<ai、hi≤109

输出

输出一共n行，每行一个整数。第i行表示第i个小朋友摘到的气球数量。

样例输入 复制

5 6 3 7 9 6 4 1 2 3 4 5 6

样例输出 复制

3 0 0 2 1

提示

来源

思路

这道题跟普通的二分题目十分的相像，而且用普通的解法也可以解出来。但是我们在这里用二分，因为其复杂度小，不容易T。

首先这里她并没有说明数据是有序的，我们先定义一个为存储儿童身高，下标的一个结构体，在排序。

sort(a+1,a+n+1,cmp) /* 由于结构体无法直接sort，所以需要自己写一个适配函数： bool cmp(qnode A,qnode B){     return A.x<B.x; } */ sort(h+1,h+m+1);

接下来跟二分就一样了，只要一直满足

h[mid]<=a[i].x

的条件，就可以继续二分下去，最后，我们还需要恢复下标：

ans[a[i].id]=res-pre; pre=res;

代码

#include<bits/stdc++.h> using namespace std; const int maxn=100005; int n,m; struct qnode{     int x,id; }a[maxn]; int h[maxn],ans[maxn]={}; bool cmp(qnode A,qnode B){     return A.x<B.x; } int main(){     scanf(%d%d,&n,&m);     for(int i=1;i<=n;i++){         scanf(%d,&a[i].x);         a[i].id=i;     }for(int i=1;i<=m;i++){         scanf(%d,&h[i]);     }sort(a+1,a+n+1,cmp);     sort(h+1,h+m+1);     int le,ri,pre=0;     for(int i=1;i<=n;i++){         int le=1;         int ri=m;         int res=0;         while(le<=ri){             int mid=(le+ri)>>1;             if(h[mid]<=a[i].x){                 res=mid;                 le=mid+1;             }else{                 ri=mid-1;             }         }ans[a[i].id]=res-pre;         pre=res;     }for(int i=1;i<=n;i++){         printf(%d\n,ans[i]);     } }

彩蛋

今天……轮到我用在线编译器了………………