hihoCoder 1496-寻找最大值

hihoCoder 1496-寻找最大值

#1496 : 寻找最大值

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

给定N个数A1, A2, A3, ... AN,小Ho想从中找到两个数Ai和Aj(i ≠ j)使得乘积Ai × Aj × (Ai AND Aj)最大。其中AND是按位与操作。

小Ho当然知道怎么做。现在他想把这个问题交给你。

输入

第一行一个数T,表示数据组数。(1 <= T <= 10)

对于每一组数据:

第一行一个整数N(1<=N<=100,000)

第二行N个整数A1, A2, A3, ... AN (0 <= Ai <220)

输出

一个数表示答案

样例输入
2
3
1 2 3
4
1 2 4 5
样例输出
12
80

给定一个数组,要求从中选出两个数a和b(它们的下标不能相同),使得乘积a*b*(a&b)最大。

这题的AC之路还挺有意思的,首先我尝试了O(n^2)的暴力方法,不出所料的TLE了,不过也得了40分。所以O(n^2)的方法肯定是不行的,我就想各种O(n)的方法。

首先分析一下a*b*(a&b),有两个部分,a*b和a&b。最优的方案当然是求a*b*(a&b)整体的最大值,但是这需要O(n^2)。次优的方案是求a*b或者a&b的最大值,然后看看整体a*b*(a&b)会不会也是最大呢。

我先考虑了a&b,因为要使a&b越大,则a和b的高位要有很多一致的'1',这样,a和b本身也就比较大,进而a*b也就比较大。但还是需要O(n^2)的时间,只不过循环过程中省略了a*b*(a&b)的计算。提交之后WA了,而且是0分,推断这种解法不可行。

后来尝试了求a*b的最大值,想法也和求a&b的最大值类似。如果a*b越大,则a,b本身也比加大,导致a&b也会比较大吧?求a*b的最大值,就好办多了,当然不能暴力两层循环,要不然又TLE。我们只需一次遍历,找到最大和次大的两个数,则他们的乘积肯定是最大的。这次提交之后,虽然也是WA,但是居然得了80分。

所以我就想,可能真的是a,b越大,则a*b*(a&b)也越大。后来一想可能会遇到a很大,二进制是10000;但是b也很大,而且是只比a小1,二进制是01111,这样虽然a*b很大,但是a&b就是0了。导致整体a*b*(a&b)是0。于是我进一步扩大了范围,记录前3大的元素first,second和third,他们之间有3个组合(first,second)、(first,third)、(second,third),只需在这3个对里面求最大就好了。我当时的想法是,虽然first和second会遇到10000和01111的情况,但是second和third可能会不会了。提交之后,居然真的AC了!

代码如下:

#include<iostream>
#include<cstdio>
#include<unordered_map>
#include<algorithm>
#include<functional>
#include<vector>
#include<climits>
#include<cfloat>
using namespace std;

typedef long long LL;
vector<LL> nums(100005, 0);

int main() {

	//freopen("input.txt", "r", stdin);

	int t, n;
	scanf("%d", &t);
	while (t--) {
		scanf("%d", &n);
		LL first = LLONG_MIN, second = LLONG_MIN, third = LLONG_MIN;
		for (int i = 0; i < n; ++i) {
			scanf("%d", &nums[i]);
			if (nums[i] > first) {
				third = second;
				second = first;
				first = nums[i];
			}
			else if (nums[i] > second) {
				third = second;
				second = nums[i];
			}
			else if (nums[i] > third) {
				third = nums[i];
			}
		}
		LL ans = max(first*second*(first&second), first*third*(first&third));
		ans = max(ans, second*third*(second&third));

		printf("%lld\n", ans);
	}
	return 0;
}

本代码提交AC,用时85MS。

后来看前几名AC的代码,好多是先对数组排序,然后从大到小求a*b*(a&b)的最大值,这样最坏复杂度还是O(n^2),但是好像也能AC。

Leave a Reply

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