原題及翻譯

Raju and Meena love to play with Marbles.
拉朱和米娜喜歡玩彈珠。
They have got a lot of marbles with numbers written on them.
他們有很多寫著數字的大理石。
At the beginning, Raju would place the marbles one after another in ascending order of the numbers written on them.
起初，拉朱會將大理石按數字的升序排列。
Then Meena would ask Raju to find the first marble with a certain number.
然后米娜會要求拉朱找到第一個有一定數量的大理石。
She would count 1…2…3.
她會數到1…2…3。
Raju gets one point for correct answer, and Meena gets the point if Raju fails.
拉朱的回答正確得1分，如果拉朱失敗，米娜得1分。
After some fixed number of trials the game ends and the player with maximum points wins.
經過一定數量的測試后，游戲結束，得分最高的玩家獲勝。
Today it’s your chance to play as Raju.
今天是你成為拉朱的機會。
Being the smart kid, you’d be taking the favor of a computer.
作為一個聰明的孩子，你會喜歡電腦。
But don’t underestimate Meena, she had written a program to keep track how much time you’re taking to give all the answers.
但不要低估米娜，她寫了一個程序來跟蹤你花了多少時間來給出所有的答案。
So now you have to write a program, which will help you in your role as Raju.
所以現在你必須寫一個程序，這將有助于你作為拉朱的角色。

Input

輸入
There can be multiple test cases.
可能有多個測試用例。
Total no of test cases is less than 65.
測試用例總數小于65。
Each test case consists begins with 2 integers: N the number of marbles and Q the number of queries Mina would make.
每個測試用例都由2個整數組成：n是大理石的數量，q是米娜要進行的查詢的數量。
The next N lines would contain the numbers written on the N marbles.
接下來的n行將包含寫在n個大理石上的數字。
These marble numbers will not come in any particular order.
這些大理石數字不會有任何特定的順序。
Following Q lines will have Q queries.
以下Q行將有Q查詢。
Be assured, none of the input numbers are greater than 10000 and none of them are negative.
請確保，輸入的數字都不大于10000，也不為負數。
Input is terminated by a test case where N = 0 and Q = 0.
輸入被一個n=0和q=0的測試用例終止。

Output

輸出
For each test case output the serial number of the case.
對于每個測試用例，輸出該用例的序列號。
For each of the queries, print one line of output.
對于每個查詢，打印一行輸出。
The format of this line will depend upon whether or not the query number is written upon any of the marbles.
這一行的格式將取決于查詢號是否寫在任何大理石上。
The two di?erent formats are described below:
兩種不同的格式如下所述：
‘x found at y’, if the first marble with number x was found at position y.
“x在y處找到”，如果在y處找到第一個帶有x號的大理石。
Positions are numbered 1, 2, . . . , N .
位置編號為1、2、。…n。
‘x not found’, if the marble with number x is not present.
?“X未找到”，如果不存在數字為X的大理石。
Look at the output for sample input for details.
有關詳細信息，請查看示例輸入的輸出。

Sample Input

4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0

Sample Output

CASE# 1:
5 found at 4
CASE# 2:
2not found
3found at 3

思路

思路其實很簡單，排序，然后查找，可以自己寫函數來做這兩件事，也可以直接用algorithm頭文件中的函數來操作。

代碼

#include <cstdio> #include <algorithm> using namespace std; const int maxn=10000; int main () {int n,q,x,a[maxn],kase=0;while(scanf("%d%d",&n,&q)==2&&n){printf("CASE# %d:\n",++kase);for(int i=0;i<n;i++){scanf("%d",&a[i]);}sort(a,a+n);while(q--){scanf("%d",&x);int p=lower_bound(a,a+n,x)-a;if(a[p]==x){printf("%d found at %d\n",x,p+1);}else{printf("%d not found\n",x);}}}return 0; }

總結

以上是生活随笔為你收集整理的《算法竞赛入门经典》 例题5-1 大理石在哪（Where is the Marble，UVa 10474）的全部內容，希望文章能夠幫你解決所遇到的問題。

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