search

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：2 描述

游戲積分的排行榜出來了，小z想看看得某個積分的人是誰。但是由于人數很多，他自己找很浪費時間，所以他想請你幫忙寫一個程序，能快速的幫他找到他想要找的人 輸入

多組測試數據，第一行有一個數T，表示有T組測試數據(T<=50)
第二行有兩個數n和m(1<=n,m<=10000)，n表示有n個人，m表示有m次查詢
接下來n行，輸入每個人的名字(長度小于10)和積分num(0<=num<=10^8)，
接下來m行，每個數表示要查詢的積分(每次查詢一定有結果)

輸出

輸出對應積分的人的名字（如果有多個人的積分相同，則輸出最前面的那個）

樣例輸入

1 5 3 zhangsan 2 qianxiao 5 liuqiang 2 wangwu 1 lisi 3 2 1 3

樣例輸出

zhangsan wangwu lisi

解題思路：先按照積分從小到大排序，然后二分查找要查找的積分，判斷這個人的積分和他前面的那個人的積分是否相同。如果不同，輸出這個人的名字；否則，說明這個人不是第一個獲得這個積分的人，再接著二分，直到找到一個不同的，輸出即可。

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; struct score {char name[11];int sco; }a[10005]; bool comp(score a1,score a2) {return a1.sco < a2.sco; } int Binary_search(int l, int r, int k) {while(l < r){int mid = (l + r) / 2;if(a[mid].sco > k)r = mid;else if(a[mid].sco < k)l = mid+1;else{if(a[mid].sco == a[mid - 1].sco)r = mid;elsereturn mid;}} } int main() {int t, n, m, i, k;scanf("%d",&t);while(t--){scanf("%d%d",&n,&m);for(i = 0; i < n; i++)scanf("%s%d",a[i].name,&a[i].sco);stable_sort(a,a+n,comp);for(i = 0; i < m; i++){scanf("%d",&k);int p = Binary_search(0,n,k);printf("%s\n",a[p].name);}}return 0; }

總結

以上是生活随笔為你收集整理的NYOJ 904 search 二分查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。