UVa 10474

題目

http://domen111.github.io/UVa-Easy-Viewer/?10474

每一筆測資有 $n$ 筆資料以及 $q$ 筆詢問

要求資料排序過後，每筆詢問的數字在資料當中第一次出現的位置，從一開始數

想法

要找排序後的位置，當然先排序好

在排序完成後，要找第一次出現的位置，那就直接帶入 lower_bound 的概念即可

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int n, q, res, arr[10010], Case=1;
int main(){
	while(cin>>n>>q && (n!=0 && q!=0)){
		for(int i=0 ; i<n ; i++){
			cin>>arr[i];
		}
		sort(arr, arr+n);
		cout<<"CASE# "<<Case++<<":\n";
		for(int i=0, m ; i<q ; i++){
			cin>>m;
			res = lower_bound(arr, arr+n, m)-arr;
			if(arr[res] == m){
				cout<<m<<" found at "<<res+1<<"\n";
			}
			else{
				cout<<m<<" not found\n";
			}
		}
	}
	return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(n)$

每筆測資找搜尋時間複雜度為 $O(logn)$

每筆測資總時間複雜度為 $O(n + qlogn)$