洛谷P1571眼红的Medusa【二分查】【map】

洛⾕P1571眼红的Medusa【⼆分查】【map】

题⽬描述

虽然Miss Medusa到了北京，领了科技创新奖，但是他还是觉得不满意。原因是，他发现很多⼈都和他⼀样获了科技创新奖，特别是其中的某些⼈，还获得了另⼀个奖项——特殊贡献奖。⽽越多的⼈获得了两个奖项，Miss Medusa就会越眼红。于是她决定统计有哪些⼈获得了两个奖项，来知道⾃⼰有多眼红。

输⼊格式：

输⼊第⼀⾏，有两个数n,m，表⽰有n个⼈获得科技创新奖，m个⼈获得特殊贡献奖。

第⼆⾏，n个正整数，表⽰获得科技创新奖的⼈的编号

第三⾏，m个正整数，表⽰获得特殊贡献奖的⼈的编号

输出格式：

输出⼀⾏，为获得两个奖项的⼈的编号，按在科技创新奖获奖名单中的先后次序输出。

输⼊样例#1：

4 3

2 15 6 8

8 9 2

输出样例#1：

2 8

说明

对于60%的数据，n<=1000，m<=1000

现代汉语语音学对于100%的数据，n<=100000，m<=100000，获得奖项的⼈的编号在2*10^9以内

g革命输⼊数据保证第⼆⾏任意两个数不同，第三⾏任意两个数不同。

解题分析：

⾸先这道题可以⽤map,⾮常⽅便。然后也可以⽤⼆分查来做，因为对第⼆个数组⽤⼆分后，整个程序的复杂度为（nlogn）（因为还要遍历⼀遍第⼀个数组），⽽数据范围为10^5，所以可⾏。

map解法

#include<bits/stdc++.h>

using namespace std;

int n, m;

apnic

map<int, bool> mapp;

int a[101000], b[101000];

int main()

{

scanf("%d%d", &n, &m);

for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); }

for (int i = 1; i <= m; i++) { scanf("%d", &b[i]); mapp[b[i]] = true; }//建⽴映射关系

for (int i = 1; i <= n; i++) if (mapp[a[i]]) cout << a[i] << "";//如果出现过直接输出

return0;

}

⼆分查

#include<iostream>

#include<cstdio>

#include<algorithm>

using namespace std;

int n, k, a[100005], b[100005];

int main()

{

scanf("%d%d", &n, &k);

for (int i = 1; i <= n; i++)scanf("%d", &a[i]);

for (int i = 1; i <= k; i++)scanf("%d", &b[i]);

sort(b + 1, b + 1 + k);

for (int i = 1; i <= n; i++)

{

int low = 1, high = k;

while (low <= high)//⼆分，查是否有相同元素

{

int mid = (low + high) / 2;米脂的婆姨性功能

if (b[mid] == a[i])

{

cout << a[i] << "";

break;

}

else if (b[mid]<a[i])low = mid + 1;

else high = mid - 1;

skyline}

}

return0;

}

知识管理系统

2018-05-27

本文发布于:2024-09-22 03:41:08，感谢您对本站的认可！

本文链接：https://www.17tex.com/xueshu/397853.html

上一篇：（番外篇1）贝叶斯超参数的确定方法（附自适应搜索法、牛顿迭代法和二分查法的python实现）

下一篇：二叉排序树平均查长度的精确表达式

标签：获得输出奖项科技数据原因

留言与评论（共有 0 条评论）