题目描述 陶陶们打算去摘一棵树上的苹果。每个苹果在树上都有一定的高度,某个陶陶能摘到的苹果高度不能超过他跳起的的高度。为了公平起见,让跳的低的陶陶先摘,跳的高的陶陶后摘。 陶陶们都很贪心,每个陶陶在摘苹果的时候都会把自己能摘的苹果都摘掉。很巧的是, 陶陶们跳起来手能够着的高度都不一样,这样就不会有跳起来后高度相同的陶陶之间发生争执了。
输入 第一行,输入两个整数N,M,其中N表示陶陶们的数量,M表示树上苹果的数量。
第二行输入 N 个正整数,第 i 个数ai表示第 i 个陶陶跳起来手能够着的高度。
第三行输入 M 个正整数,第 i 个数 hi表示第 i 个苹果的高度。
输出 一共 n 行,每行一个整数。第 i 行表示第 i 个陶陶摘到的苹果数量。
样例输入 Copy 【输入样例1】 5 6 3 7 9 6 4 1 2 3 4 5 6
【输入样例2】 10 10 1 2 3 4 5 6 7 8 9 10 3 1 4 6 7 8 9 9 4 12 样例输出 Copy 【输出样例1】 3 0 0 2 1
【输出样例2】 1 0 1 2 0 1 1 1 2 0 提示 【样例1解释】摘取苹果的顺序依次为 1, 5, 4, 2, 3号陶陶。1号陶陶能摘1,2,3号苹果,5 号陶陶能摘 4 号苹果,4 号陶陶能摘 5, 6 号苹果,2, 3 号陶陶没有苹果可摘了。
#include<bits/stdc++.h>
using namespace std;
struct N
{
int sum;
int gd;
int xb;
}a[100005];
int h[100005],s=1;
bool cmp(N a,N b)
{
return a.gd<b.gd;
}
bool cmp1(N a,N b)
{
return a.xb<b.xb;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i].gd;
a[i].sum=0;
a[i].xb=i;
}
for(int i=1;i<=m;i++)
cin>>h[i];
sort(a+1,a+n+1,cmp);
sort(h+1,h+m+1);
for(int i=1;i<=m;i++)
{
if(h[i]>a[n].gd||s>n) break;
if(h[i]<=a[s].gd) a[s].sum++;
else
{
s++;
i--;
}
}
sort(a+1,a+n+1,cmp1);
for(int i=1;i<=n;i++)
cout<<a[i].sum<<endl;
return 0;
}
TLE了!