算法竞赛入门经典(第二版) | 例题5-1 大理石在哪 (普适查找)(UVa10474,Where is the Marble?)
程序员文章站
2024-03-18 23:30:10
...
大意:
给一序列,要求先将序列排序。再给n个数字,找到每个数字在序列中的位置
题目(提交)网址→UVa-10474
百度翻译→百度翻译
没使用过该网站的同学请猛戳这里→vJudge教程
思路
数组存入,sort排序,find或lower_bound查找。
分析:
最开始没有注意到n是有上限的,于是开了一个vector(小声哔哔,vector比数组慢了一倍有余),将vector换成数组就是最佳解法了,第一个代码是用find进行查找的。
代码1(find):
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int n, q;
vector <int> v;
int num = 1;
while(cin>>n>>q && n) {
while(n--) { int x; cin >> x; v.push_back(x); }
sort(v.begin(), v.end());
cout << "CASE# " << num << ":" << endl;
while(q--) {
int x; cin >> x;
vector<int>::iterator it, it1;
//查找三部曲
int size = v.size();
it = find(v.begin(), v.end(), x); //查找,如果没找到,返回end() ,一般都是0
it1 = v.begin();
//如果此处是(*it)>0,则会漏掉0,所以判断是否查找成功的条件有两个:it!=end()且*it == x;
(((it-it1)!=size) && (*it) == x) ? cout << x << " found at " << (it-it1+1) << endl : cout << x << " not found" << endl;
}
num++;
v.clear();
}
return 0;
}
下一个代码是用lower_bound查找的。
代码2(lower_bound)
#include<bits/stdc++.h>
using namespace std;
int n, m, a[100010], q, *p, num=0;
int main() {
while (cin >>n >>m && (n != 0 && m != 0)) {
for (int i = 0; i < n; i ++) cin >>a[i];
sort(a, a+n); // 升序排列
printf("CASE# %d:\n", ++num);
while (m --) {
cin >>q;
p = lower_bound(a, a+n, q); // 找到>=q的第一个数
if (p - a != n && *p == q) printf("%d found at %d\n", q, p-a+1); // 存在且为q
else printf("%d not found\n", q);
}
}
return 0;
}
收获:
1、algorithm查找的用法
2、lower_bound(a, a+n, q); // 找到>=q的第一个数
3、upper_bound(a, a+n, q); // 找到>q的第一个数
4、vector很慢。主要面向方便 。
5、最开始对题意理解有偏差,忘记严格按照:
做题步骤:
1、理解题意
2、输入输出格式(最大值限制),结束格式
3、测试规则
4、思路
5、代码实现
执行了 。 以为没有给n的大小的限制。
总结:
虽然是个大水题,但还是让笔者巩固了find查找的知识,代码中判断查找两个条件判断缺一不可,且适用于所有类型(数组、字符串、容器)。 以后可以只用这一种。不需要费力记忆和区分memchr或string头文件的查找了。
上一篇: 学军中学图灵杯趣味编程邀请赛题解 —— B. 回文串
下一篇: 2018南昌邀请赛网络赛d题