开启辅助访问 切换到宽版

奇迹创客社区

 注册
 登录
搜索
热搜: NOIP OIer 神牛
信息学基地社区»论坛 › 青少年信息学 › 信息学奥赛 › OJ题解 › 1853 【抢气球】
返回列表 发新帖
查看: 378|回复: 3

1853 【抢气球】

[复制链接]
Ethan

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
发表于 2022-7-24 18:01:09 | 显示全部楼层 |阅读模式
本帖最后由 Ethan 于 2023-3-19 09:06 编辑

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

输出一共n行，每行一个整数
第i行表示第i个小朋友摘到的气球数量
代码已AC
就是时间内存有一点大
回复

使用道具 举报

Ethan

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
 楼主| 发表于 2022-7-24 18:01:42 | 显示全部楼层
  1. #include<bits/stdc++.h>
  2. using namespace std;

  4. const int maxn=1000000;
  5. int n,m;

  7. struct children{
  8.     int x,id;
  9. }

  11. a[maxn];
  12. int h[maxn],ans[maxn]={};

  14. bool cmp(children A,children B){
  15.     return A.x<B.x;
  16. }

  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

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
 楼主| 发表于 2022-7-24 18:02:49 | 显示全部楼层
本帖最后由 Ethan 于 2022-8-4 11:02 编辑

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

使用道具 举报

tiger

主题

帖子

0

积分

新手上路

Rank: 1

积分
0
发表于 2023-8-22 10:54:55 | 显示全部楼层
  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
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

津ICP备19006949号-1 | 津公网安备12010102000465号

快速回复 返回顶部 返回列表