当前位置:首页 > 排序 > 正文
计蒜客17293抢气球
3020+

题目大意:n个小朋友抢m个气球,矮的小朋友先抢,且能抢多少个就抢多少个,请问最后每个小朋友分别抢到多少气球?

计蒜客-摩比信息学训练营的教室的墙上挂满了气球,五颜六色,小朋友们非常喜欢。

刚一下课,小朋友们就打算去抢这些气球。每个气球在墙上都有一定的高度,只有当小朋友跳起来时,手能够到的高度大于等于气球的高度,小朋友才能摘到这个气球。为了公平起见,老师让跳的低的小朋友先摘,跳的高的小朋友后摘。小朋友都很贪心,每个小朋友在摘气球的时候都会把自己能摘的气球都摘掉。

很巧的是,小朋友们跳起来手能够着的高度都不一样,这样就不会有跳起来后高度相同的小朋友之间发生争执了。

输入格式

第一行输入两个空格分隔的整数 ,其中 表示小朋友的数量, 表示墙上气球的数量。

第二行输入 个正整数(每两个整数之间用空格隔开),第 个数为 ,表示第 个小朋友跳起来手能够着的高度为

第三行输入 个正整数(每两个整数之间用空格隔开),第 个数为 ,表示第 个气球的高度为

输出格式

输出一共 行,每行一个整数。

行表示第 个小朋友摘到的气球数量。

数据范围和约定

测试点编号 特殊性质
1,2,3,4
5,6,7,8 输入的 依次递增
9,10,11,12
13,14 所有气球的高度一样
15,16
17,18,19,20

样例解释 1

对于第一组样例输入,摘取气球的顺序依次为 号小朋友。 号小朋友能摘 号气球, 号小朋友能摘 号气球, 号小朋友能摘 号气球, 号小朋友没有气球可摘了。

样例输入1

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

样例输出1

3
0
0
2
1

样例输入2

10 10
1 2 3 4 5 6 7 8 9 10
3 1 4 6 7 8 9 9 4 12

样例输出2

1
0
1
2
0
1
1
1
2
0

解题思路

矮的小朋友先抢气球,小朋友需要从矮到高进行排序;一个小朋友抢气球,肯定能把他能抢到的最高的气球以及更低的气球都抢完,因此,气球也是从小到大被抢走,也需要从低到高进行排序。排好序后,一个一个小朋友去抢气球,每个气球只会被抢一次,因此可以利用单调队列保证每个气球只被访问一次。最后是想怎么处理高度和编号的问题?索引排序!开一个数组记录小朋友的编号,抢气球的时候,高度小的编号先抢气球,抢到的气球累加到该编号的气球数里面,最后依次输出各个编号的气球数。

程序实现

About

坚决不Copy代码!

本文标签:,,,,

计蒜客17293抢气球:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!