回答哪个大理石上写着x

时间:2019-09-26 14:24来源:快三平台下载编程
描述 现有N个大理石,每个大理石上写了一个非负整数、首先把各数从小到大排序 然后回答Q个问题。每个问题问是否有一个大理石写着某个整数x,如果是,还要 回答哪个大理石上写着

描述

现有N个大理石,每个大理石上写了一个非负整数、首先把各数从小到大排序
然后回答Q个问题。每个问题问是否有一个大理石写着某个整数x,如果是,还要
回答哪个大理石上写着x。排序后的大理石从左到右编号为1~N。(在样例中,为了
节约篇幅,所有大理石的数合并到一行,所有问题也合并到一行。)

样例输入:
4 1
2 3 5 1
5
5 2
1 3 3 3 1
2 3

样例输出:
CASE# 1:
5 found at 4
CASE# 2:
2 not found
found at 3

图片 1图片 2

 1 #include <iostream> 2 #include <algorithm> 3  4 using namespace std; 5  6 main() 7 { 8     int n, q, x, a[10000], k = 0; 9     while(cin >> n >> q)10     {11         cout << "CASE#" << k << ":" << endl;12         k++;13         for(int i = 0; i < n; i++)14         {15             cin >> a[i];16         }17         sort(a, a+n);18         while(q--)19         {20             cin >> x;21             int p = lower_bound(a, a+n, x) - a; //在已知数组a中寻找x22             if(a[p] == x)23                 cout << x << " found at " << p << endl;24             else25                 cout << x << " not found" << endl;26         }         27     }28 }

View Code

STL中关于二分查找的函数有三个lower_bound 、upper_bound 、binary_search 。这三个函数都运用于有序区间(当然这也是运用二分查找的前提),下面记录一下这两个函数。

ForwardIterlower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。

ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于值val的位置。

以上函数和二分查找可参考:

编辑:快三平台下载编程 本文来源:回答哪个大理石上写着x

关键词: