欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法竞赛入门经典(第二版) | 例题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头文件的查找了。