当前位置:首页 > 题解目录 > 正文内容

【题解】开花

亿万年的星光3年前 (2022-03-12)题解目录1432

【题目描述】

小A所在的学校又迎来了一年一度的开花活动,有 n 名学生被评为文学优秀奖,m 名学生被评为体育优秀奖。现已知两个奖项获奖同学的编号,每个同学都有唯一的编号。只有同时被评为文学优秀奖和体育优秀奖的学生才能开花,小A想知道开花的名单,请你帮他统计一下。

【输入描述】


第一行两个整数 n,m\ (1\le n,m \le 10^5) ,分别表示文学优秀奖和体育优秀奖的获奖人数。

第二行 n 个不同的整数,表示获得文学优秀奖的同学编号。

第二行 m 个不同的整数,表示获得体育优秀奖的同学编号。

所有编号为正整数且不超过 10^9 。

【输出描述】


一行若干个空格分隔的整数,表示开花的同学编号,按文学优秀奖的先后次序输出。

【样例输入】

4 4
5 1 7 3
2 3 4 1

【样例输出】

 1 3

【题目分析】

根据样例,我们知道获得文学优秀奖的同学有 5 1 7 3,获得体育优秀奖的同学有 2 3 4 1。那么同时获得文学优秀奖和体育优秀奖的同学是 1 和 3,题目要求按照文学优秀奖获奖顺序输出。故而输出的结果是 3 1。

由于数据最大可能是 10^5,故算法必须优于 O(nlogn)。同时我们需要在体育优秀奖里搜索获得文学优秀奖名单。所以可以考虑用二分查找,这样算法的复杂度为 O(logn)。

1、读入文学优秀奖同学,存入数组 a。

2、读入体育优秀奖同学,存入数组 b。

3、排序数组 b,因为要在体育优秀奖里搜索文学优秀奖名单。

4、遍历数组 a,查看 a[i] 是否在数组 b 中。


【参考代码1】

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e5+6;
const int MAXM = 1e5+6;
int a[MAXN];//文学优秀奖
int b[MAXM];//体育优秀奖
 
int main() {
    //读入数据
    int n,m,i;
 	cin>>n>>m; 
    //读入文学优秀奖
    for (i=0; i<n; i++) {
        cin>>a[i];
    }
    //读入体育优秀奖
    for (i=0; i<m; i++) {
          cin>>b[i];
    }
    //排序
    sort(b, b+m);
    for (i=0; i<n; i++) {
        if (binary_search(b, b+m, a[i])) {
            cout<<a[i]<<" ";
        }
    }
    printf("\n");
 
    return 0;
}


【参考代码2】

#include<bits/stdc++.h>
using namespace std;
int t[100005];
int w[100005];
int binary_search(int x, int l, int r){
    while(l <= r){
        int mid = (l + r) >> 1;
        if(t[mid] == x){
            return mid;
        }
        if(t[mid] < x){
            l = mid + 1;
        }else{
            r = mid - 1;
        }
    }
    return -1;
}
int main(){
    int n, m;
    cin >> n >> m;
    for(int i = 0; i < n; ++i){
        cin >> w[i];
    }
    for(int i = 0; i < m; ++i){
        cin >> t[i];
    }
    sort(t, t + m);
    int t = 0;
    for(int i = 0; i < n; ++i){
        if(binary_search(w[i], 0, m - 1) != -1){
            t++;
            if(t == 1) cout << w[i];
            else{
                cout << " " << w[i];
            }
            
        }
    }
    return 0;
}


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

标签: 二分
分享给朋友:

相关文章

【题解】跳格子

【题目描述】地面上有一排长度为n的格子1-n,每个格子上都有一个数xi,开始时你在位置0,每次你可以向前跳1-2格,然后取走格子上的数,直到跳到位置n+1。取走的数的和就是你的得分,现在你想知道你可能...

【题解】合并有序表

【题目描述】k路归并问题把k个有序表合并成一个有序表。元素共有n个。【输入描述】读入K。接下来K行。每i行第一个数为Ci表示接下来这一行有Ci个数,表示第i个序列。总数小于100000。【输出描述】输...

【题解】自动晾衣机

【题目描述】有一个环形可以晾衣服的衣架,有若干个夹子组成,它可以晾不同长度的衣服(占用多个夹子),并且每两件衣服中间要有一个空夹子作为空位,下面需要依次晾干几件长度不一的衣服,请你给出某个夹子的使用情...

【题解】合唱队形

【题目描写】N位同学站成一排,音乐老师要请其中的(N−K)位同学出列,使得剩下的KK位同学排成合唱队形。合唱队形是指这样的一种队形:设K位同学从左到右依次编号为1,2,…,K,他们的身高分别为T1,T...

【题解】开关灯(1)

【题目描述】假设有N盏灯(N为不大于5000的正整数),从1到N按顺序依次编号,初始时全部处于开启状态;有M个人(M为不大于N的正整数)也从1到M依次编号。第一个人(1号)将灯全部关闭,第二个人(2号...

整理药名

【题目描述】医生在书写药品名的时候经常不注意大小写,格式比较混乱。现要求你写一个程序将医生书写混乱的药品名整理成统一规范的格式,即药品名的第一个字符如果是字母要大写,其他字母小写。如将ASPIRIN、...