【題目敘述】https://codeforces.com/problemset/problem/1288/D
【解題想法】二分搜，位元運算
- 【例子】題目給出6個陣列:
- a1 = [5 0 3 1 2]
- a2 = [1 8 9 1 3]
- a3 = [1 2 3 4 5]
- a4 = [9 1 0 3 7]
- a5 = [2 3 0 6 3]
- a6 = [6 4 1 7 0]
- 挑選其中兩個陣列（可以選擇同一個陣列兩次），形成一個新陣列。新陣列的每個元素為原來兩個陣列的「最大值」。
- 比如，此例答案為 a1 和 a5，形成的新陣列為 [5 3 3 6 3]。
- 題目要求，找出兩個陣列，讓 min ( [5 3 3 6 3] ) = 3 的值最大。
- 【做法】二分搜，找出 x 值，使用 x 來檢查每個陣列的每個元素，利用位元表示每一個元素是否大於等於 x。
- 例如：陣列 a1 = [5 0 3 1 2] 在 x = 5 時的位元表示式為 10000。如果存在另一個陣列 (ai) 的位元表示式與 10000 「OR 之後的結果」為 11111，則表示此 x 是可行的答案，而 a1 與 ai 是其中一組解。
- 找出最大的 x 值，印出一組符合條件的陣列編號。
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int a[300005][8];
int a1, a2;
bool check(int x){
// 2^m 種位元組合，初始值-1（沒有任一陣列歸類其中）
vector <int> mask(1 << m, -1);
for (int i=0; i<n; i++){
int now = 0;
for (int j=0; j<m; j++){
if (a[i][j] >= x){
now |= (1 << j);
}
}
mask[now] = i; //第i個陣列屬於這種位元組合
}
//有某個陣列所有元素均大於x
//選擇兩個陣列為同一陣列
if (mask[(1 << m) - 1] != -1){
a1 = a2 = mask[(1 << m) - 1];
return true;
}
//枚舉所有可能的配對
for (int i=0; i< (1 << m); i++){
for (int j=0; j< (1 << m); j++){
if (mask[i] != -1 && mask[j] != -1 && (i | j) == (1 << m) - 1){
a1 = mask[i];
a2 = mask[j];
return true;
}
}
}
return false;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m;
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
cin >> a[i][j];
}
}
int l = 0;
int r = 1e9 + 100;
while (r - l > 1){
int mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
cout << a1 + 1 << ' ' << a2 + 1 << '\n';
return 0;
}