題目
時(shí)間限制:10000ms
單點(diǎn)時(shí)限:1000ms
內(nèi)存限制:256MB
描述
給定N個(gè)數(shù)A1, A2, A3, ... AN玛荞，小Ho想從中找到兩個(gè)數(shù)Ai和Aj(i ≠ j)使得乘積Ai × Aj × (Ai AND Aj)最大近刘。其中AND是按位與操作棺妓。
小Ho當(dāng)然知道怎么做。現(xiàn)在他想把這個(gè)問(wèn)題交給你。
輸入
第一行一個(gè)數(shù)T，表示數(shù)據(jù)組數(shù)。(1 <= T <= 10)
對(duì)于每一組數(shù)據(jù)：
第一行一個(gè)整數(shù)N（1<=N<=100,000）
第二行N個(gè)整數(shù)A1, A2, A3, ... AN (0 <= Ai <220)
輸出
一個(gè)數(shù)表示答案
樣例輸入
2
3
1 2 3
4
1 2 4 5
樣例輸出
12
80
分析
- 大概可以認(rèn)為 這兩個(gè)數(shù)都要比較大才有可能是最大值抖剿；
- 然后，窮舉最大的1000個(gè)數(shù)识窿。斩郎。。就AC了喻频。缩宜。。
- hihocoder上有不少題都能這樣解甥温。
代碼
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int n = 0;
static int en = 0;
static long[] dat = new long[1 << 17];
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int t = cin.nextInt();
while (t-- != 0) {
n = cin.nextInt();
for (int i = 0; i < n; ++i)
dat[i] = cin.nextLong();
Arrays.sort(dat, 0, n);
for (int left = 0, right = n - 1; left < right; ++left, --right) {
long tmp = dat[left];
dat[left] = dat[right];
dat[right] = tmp;
}
long best = 0;
en=n>1000?1000:n;
for (int i = 0; i < en; ++i) {
long ci=dat[i];
for (int j = i + 1; j < en; ++j) {
long cur=ci*dat[j]*(ci&dat[j]);
if(cur>best) best=cur;
}
}
System.out.println(best);
}
cin.close();
}
}
