hihoCoder 1128-二分·二分查找

hihoCoder 1128-二分·二分查找

#1128 : 二分·二分查找
时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述
Nettle最近在玩《艦これ》,因此Nettle收集了很多很多的船(这里我们假设Nettle氪了很多金,开了无数个船位)。去除掉重复的船之后,还剩下N(1≤N≤1,000,000)种不同的船。每一艘船有一个稀有值,任意两艘船的稀有值都不相同,稀有值越小的船越稀有,价值也就越高。
Nettle现在通过大建又造出了一艘船,他想知道这艘船是不是重复的。如果是重复的,那么这艘船在Nettle所有的船里面稀有值排多少位。

问题一

Nettle已经先把自己所有船按照稀有值从小到大排列好了(a[1..N]),我们要做的是看看新得到的船(假设稀有值为K)是否在这个序列中,且有对应的a[i]=K时,i为多少?
提示一:有序数组的二分查找

问题二

因为Nettle的船太多了,他不愿意去给所有船按照稀有值排序,而是直接告诉了我们每一艘船的稀有值。在这种情况下我们该如何解决这个问题呢?
提示二:非有序数组的二分查找

输入
第1行:2个整数N,K。N表示数组长度,K表示需要查找的数;
第2行:N个整数,表示a[1..N],保证不会出现重复的数,1≤a[i]≤2,000,000,000。

输出
第1行:一个整数t,表示K在数组中是第t小的数,若K不在数组中,输出-1。

样例输入
10 5180
2970 663 5480 4192 4949 1 1387 4428 5180 2761

样例输出
9


给出一串数字,问某个数字K在该序列中是第几小的。

最简单的解法,遍历一遍数组,找出比K小的数的个数n,则K是第n+1小的数。完整代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int n, k;
int main()
{
	scanf("%d %d", &n, &k);
	a.resize(n);
	bool is_exist = false;
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		if (a[i] == k)
			is_exist = true;
		if (a[i] < k)
			ans++;
	}
	if (!is_exist)
		printf("-1\n");
	else
		printf("%d\n", ans + 1);
	return 0;
}

本代码提交AC,用时58MS,内存3MB。

但是题意显然不是用这种方法,为了配合下一题的求第k小数,提示使用快排的中间步骤,依次将序列划分成比某个数大和比某个数小的两部分,再在其中某个子序列中递归求解。完整代码如下:

#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> a;
int n, k;
int GetOrder(int p, int q)
{
	int m = a[p];
	int i = p, j = q;
	while (i < j)
	{
		while (i < j&&a[j] > m)
			j--;
		a[i] = a[j];
		while (i < j&&a[i] < m)
			i++;
		a[j] = a[i];
	}
	if (k == m)
		return i;
	else if (k < m)
		return GetOrder(p, i - 1);
	else
		return GetOrder(i + 1, q);
}
int main()
{
	//freopen("input.txt", "r", stdin);

	scanf("%d %d", &n, &k);
	a.resize(n);
	bool is_exist = false;
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		if (a[i] == k)
			is_exist = true;
	}
	if (!is_exist)
		printf("-1\n");
	else
		printf("%d\n", GetOrder(0, n - 1) + 1);
	return 0;
}

本代码提交AC,用时57MS,内存3MB。

Leave a Reply

Your email address will not be published. Required fields are marked *