算法入门经典：大理石在哪儿

大理石在哪儿（where is the marble？ ， UVa 10474） 前言：好好努力，在研一参加一次关于ＡＣＭ竞赛，完成本科的期望。 问题： 现有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

3 found at 3 

代码： //大理石在哪 #include <cstdio> #include <algorithm> using namespace std; const int maxn = 10000; int main() { int num, ques, x, a[maxn], kase = 0; while(scanf("%d%d", &num, &ques) == 2 && num){ printf("CASE# %d:\n", ++kase); for(int i = 0; i < num; i++) scanf("%d", &a[i]); sort(a, a+num); //排序 while(ques --){ scanf("%d", &x); int p = lower_bound(a, a+num, x) - a; //在已排序数组a中找x if(a[p] == x) printf("%d found at %d\n", x, p+1); else printf("%d not found\n", x); } } return 0; } 总结：

主要学习了ＳＴＬ，然后就是 lower_bound( ) ；

int p = lower_bound(a, a+num, x) - a;这段代码让我思考好一会，主要是因为忘了ａ是一个数组， lower_bound( )返回的是一个迭代器，－ａ相当于减去ａ的首地址，返回的ｐ即是它们之间的距离。

关于此函数的拓展使用：

一个数组number序列为：4,10,11,30,69,70,96,100.设要插入数字3,9,111.pos为要插入的位置的下标则（注：number为数组名）

pos = lower_bound( number, number + 8, 3) - number，pos = 0.即number数组的下标为0的位置。 pos = lower_bound( number, number + 8, 9) - number， pos = 1，即number数组的下标为1的位置（即10所在的位置）。 pos = lower_bound( number, number + 8, 111) - number， pos = 8，即number数组的下标为8的位置（但下标上限为7，所以返回最后一个元素的下一个元素）。