1853 【抢气球】

Ethan

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

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

第三行输入m个正整数（每两个整数之间用空格隔开），第i个数为hi，表示第i个气球的高度为hi

输出一共n行，每行一个整数

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

代码已AC

就是时间内存有一点大

Ethan

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. const int maxn=1000000;
   
5. int n,m;
   
6. 
   
7. struct children{
   
8.     int x,id;
   
9. }
   
10. 
    
11. a[maxn];
    
12. int h[maxn],ans[maxn]={};
    
13. 
    
14. bool cmp(children A,children B){
    
15.     return A.x<B.x;
    
16. }
    
17. 
    
18. int main(){
    
19.     scanf("%d%d",&n,&m);
    
20.     for(int i=1;i<=n;i++){
    
21.         scanf("%d",&a[i].x);
    
22.         a[i].id=i;
    
23.     }
    
24.         for(int i=1;i<=m;i++){
    
25.         scanf("%d",&h[i]);
    
26.     }
    
27.     stable_sort(a+1,a+n+1,cmp);
    
28.     stable_sort(h+1,h+m+1);
    
29.     int z,x,c=0;
    
30.     for(int i=1;i<=n;i++){
    
31.         int z=1;
    
32.         int x=m;
    
33.         int q=0;
    
34.         while(z<=x){
    
35.             int w=(z+x)>>1;
    
36.             if(h[w]<=a[i].x){
    
37.                 q=w;
    
38.                 z=w+1;
    
39.             }
    
40.                         else{
    
41.                 x=w-1;
    
42.             }
    
43.         }
    
44.                 ans[a[i].id]=q-c;
    
45.         c=q;
    
46.     }
    
47.         for(int i=1;i<=n;i++){
    
48.         printf("%d\n",ans[i]);
    
49.     }
    
50.         return 0;
    
51. }

复制代码

Ethan

使用stable_sort是为了让稳定性更佳

tiger

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. #define int long long
   
5. bool cmp(int x,int y){
   
6.         return x<y;
   
7. }
   
8. signed main(){
   
9.     int n;//number of chidren
   
10.     cin>>n;
    
11.     int m;//number of ballon
    
12.     cin>>m;
    
13.     int a[100005],h[100005],jc[100005]={0},jb[100005]={0};//a mean chidren's high
    
14.     for(int i=0;i<n;i++) cin>>a[i];
    
15.     for(int i=0;i<m;i++) cin>>h[i];
    
16.     sort(a,a+n,cmp);
    
17.     for(int i=0;i<n;i++){
    
18.             for(int j=0;j<m;j++){
    
19.                     if(a[i]>=h[j]&&jb[j]==0){
    
20.                             jc[i]++;
    
21.                             jb[j]=1;
    
22.                     }
    
23.                 }
    
24.         }
    
25.         for(int i=0;i<n;i++) cout<<jc[i]<<'\n';
    
26.     return 0;
    
27. }

复制代码

求楼主帮我解决TLE