題目描述

雖然 Miss Medusa 到了北京，領(lǐng)了科技創(chuàng)新獎，但是她還是覺得不滿意。原因是：他發(fā)現(xiàn)很多人都和她一樣獲了科技創(chuàng)新獎，特別是其中的某些人，還獲得了另一個獎項——特殊貢獻獎。而越多的人獲得了兩個獎項，Miss Medusa就會越眼紅。于是她決定統(tǒng)計有哪些人獲得了兩個獎項，來知道自己有多眼紅。

輸入格式

第一行兩個整數(shù)?n, mn,m，表示有?nn?個人獲得科技創(chuàng)新獎，mm?個人獲得特殊貢獻獎。

第二行?nn?個正整數(shù)，表示獲得科技創(chuàng)新獎的人的編號。

第三行?mm?個正整數(shù)，表示獲得特殊貢獻獎的人的編號。

輸出格式

輸出一行，為獲得兩個獎項的人的編號，按在科技創(chuàng)新獎獲獎名單中的先后次序輸出。

輸入輸出樣例

輸入 4 3 2 15 6 8 8 9 2 輸出 2 8

說明/提示

對于?60\%60%?的數(shù)據(jù)，0 \leq n, m \leq 10000≤n,m≤1000，獲得獎項的人的編號?\lt 2 \times 10^9<2×109；

對于?100\%100%?的數(shù)據(jù)，0 \leq n, m \leq 10^50≤n,m≤105，獲得獎項的人的編號?\lt 2 \times 10^9<2×109。

輸入數(shù)據(jù)保證第二行任意兩個數(shù)不同，第三行任意兩個數(shù)不同。

解題思路：尋找兩獎均獲得的人，相當于在一組數(shù)據(jù)中查找與另一組數(shù)據(jù)相同的數(shù)據(jù)。

二分查找又稱折半查找，使用其前提條件是數(shù)據(jù)要有序，因此在下面代碼中先將選擇的一組數(shù)據(jù)進行排序，使用了sort函數(shù)，sort函數(shù)默認排序是升序的。

C++代碼

#include<bits/stdc++.h> using namespace std; int n,m,tech[100005],special[100005]; int main() {scanf("%d%d",&n,&m);//n個人獲得科技創(chuàng)新獎，m個人獲得特殊貢獻獎for(int i=1;i<=n;i++){scanf("%d",&tech[i]);//科技創(chuàng)新獎獲得者的編號}for(int i=1;i<=m;i++){scanf("%d",&special[i]);//特殊貢獻獎獲得者的編號}sort(special+1,special+1+m);//用特殊貢獻獎獲得者的編號進行排序for(int i=1;i<=n;i++)//用科技創(chuàng)新獎獲得者的編號去尋找特殊貢獻獎獲得者的編號是否存在相同{//二分算法 int low=1,high=m;while(low <= high){int mid = (low+high)/2;if(special[mid] == tech[i])//判斷兩者編號是否相同 {cout<<tech[i]<<" ";break;}else if(special[mid] < tech[i])low = mid+1;//在右區(qū)間找else high = mid-1;//在左區(qū)間找}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的洛谷 1571 眼红的Medusa的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。