D - Minimax Problem （二分、状压）

深藏阁楼爱情的钟 2021-07-16 14:38 317阅读 0赞

[题目][Link 1]

思路：首先暴力想一想这道题，把每两组数都模拟一遍取最大值，O(N^2)。然后看有没有什么地方可以改进，会发现这题可以适用于二分，看可以用二分的条件—单调（而本题从某种方面看也是“单调”的，所要求的最大值ans,值越小就越不可能成立，越大则越可能成立）,故设立一个范围l=0,r=1e9，二分出答案。

check()该怎么弄？如check(a)，当存在两个数组lst1,lst2任意第i位元素的两者最大值 --max(lst1\[i\],lst2\[i\])>=a，则a是符合条件的，最终的答案>=a,l=a。现在我们只需解决如何知道是否存在两个数组任意一位的最大都>=a即可。  
看到数组长度最多只有8位，那么可以把一个数组状压成一个整数来表示，二进制第i位为1代表这个数组第i位>=a，第i位为0代表这个数组第i位<a。最后再遍历看能否找出两个数组满足(lst1|lst2)==1<<(m-1)-1，细节见代码。

Code:

#include<iostream>
    #include<map>
    #define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
    using namespace std;
    typedef long long ll;
    const int Max = 1e6 + 5;
    int lst[Max][10];
    int n, m, a1, a2;
    map<int, int> ma;
    int check(int a)
    { 
    	ma.clear();
    	for (int i = 1;i <= n;i++)
    	{ 
    		int sum = 0;
    		for (int j = 1;j <= m;j++)
    		{ 
    			if (lst[i][j] >= a)sum |= (1 << (j - 1));
    		}
    		ma[sum] = i;
    	}
    	for (int i = 0;i < (1 << m) ;i++)
    	{ 
    		for (int j = 0;j < (1 << m);j++)
    		{ 
    			if (ma[i] && ma[j] && (i | j) == (1 << m) - 1)
    			{ 
    				a1 = ma[i], a2 = ma[j];
    				return 1;
    			}
    		}
    	}
    	return 0;
    }
    
    int main()
    { 	
    	FAST;
    	cin >> n >> m;
    	for (int i = 1;i <= n;i++)
    		for (int j = 1;j <= m;j++)cin >> lst[i][j];
    	int l = 0, r = 1e9;
    	while (l < r)
    	{ 
    		int mid = (l + r + 1) / 2;
    		if (check(mid))l = mid;
    		else r = mid - 1;
    	}
    	check(l);
    	cout << a1 << " " << a2;
    }

[Link 1]: https://codeforc.es/contest/1288/problem/D