抢气球

题目要求

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

输入格式

第一行输入两个空格分隔的整数 n,m(1≤n,m≤10⁵), 其中 n 表示小朋友的数量，m表示墙上气球的数量。
第二行输入 n个正整数（每两个整数之间用空格隔开），第 i个数为 a_i(a_i≤10⁹)，表示第 i个小朋友跳起来手能够着的高度为a_i。
第三行输入 i 个数为 h_i(1≤h_i≤109)表示第 i 个气球的高度为 h_i

输出格式

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

算法分析

因为输入和编号有关，我们定义一个结构体记录编号和高度，如果数据小的情况下两个循环，对结构体数组排序，每一个小朋友遍历一遍气球，符合的答案加加，气球拿掉就行，但是题目中给的数据范围大，所有不能用这种两个for循环复杂度为n*m，因为计算机中每秒最大运行的时间复杂度为10⁸，这样的话算下来时间复杂度为10¹⁰，超过了限定，那么我们对结构体数组和气球高度数组进行sort排序，小朋友拿掉的气球就不再遍历，这样的话n个小朋友加m个气球总共的时间复杂度为每个都访问一遍就是n+m，远远没有达到限定，上面sort函数的复杂度为n * lgⁿ，加上去的话也没有达到题目的要求，这样就可以成功的解出这道题目来

代码解析

#include
#include
#include
#include
#include
using namespace std;
struct student{int num;int height;
};
bool cmp(student x,student y){return x.height<y.height; 
}
int main(){student stu[100005];int wall[100005];int ans[100005];int n,m;cin>>n>>m;//n小朋友 for(int i=0;i<n;i++){cin>>stu[i].height;stu[i].num=i+1;}for(int i=0;i<m;i++){cin>>wall[i];} sort(stu,stu+n,cmp);sort(wall,wall+m);int p=0;for(int i=0;i<n;i++){while(p<m&&stu[i].height>=wall[p]){ans[stu[i].num]++;p++;}} for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return 0;
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！