hihoCoder 1496-寻找最大值

---

给定一个数组，要求从中选出两个数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了！ 代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时85MS。 后来看前几名AC的代码，好多是先对数组排序，然后从大到小求a*b*(a&b)的最大值，这样最坏复杂度还是$$O(n^2)$$，但是好像也能AC。]]>