You are given 𝑛 arrays 𝑎1, 𝑎2, ..., 𝑎𝑛; each array consists of exactly 𝑚 integers. We denote the 𝑦-th element of the 𝑥-th array as 𝑎𝑥,𝑦.
You have to choose two arrays 𝑎𝑖 and 𝑎𝑗 (1≤𝑖,𝑗≤𝑛, it is possible that 𝑖=𝑗). After that, you will obtain a new array 𝑏 consisting of 𝑚 integers, such that for every .
Your goal is to choose and so that the value of min is maximum possible.
大致题意 📖
给你 个数组,每个数组有 个数
选择两个数组 , 可以等于
定义数组的每个项 .
定义
求,使最大
链接 🔗
「CodeForces 1288D」 Minimax Problem
题解 ❓
直接求显然很麻烦,注意到(m <= 8)我们考虑二分
单调性很显然,可以感性理解
接着考虑如何判断是否满足条件
直接枚举是的,但是因为我们只需要验证是否能每项都大于,所以我们可以将每个大于等于的数变成1,小于的数变成0
这样的所有数组都会变成最多长为8位的数组,最多有个不同的数组
因此我们可以直接枚举这个数组 ,即考虑是否存在两个数组的或 全为
代码
const int maxd = 3e5+10;
ll a[maxd][10],ansl,ansr,n,m,vis[300];
bool check(ll x)
{
memset(vis,0,sizeof(vis));
FOR(i,1,n)
{
ll now = 0;
FOR(j,1,m) if(a[i][j] >= x) now |= 1<<(j-1);
vis[now] = i;
}
F(1<<m)
FOR(j,0,(1<<m)-1)
if(vis[i] && vis[j] && ( (i|j) == (((1<<m)-1))))
{
ansl = vis[i], ansr = vis[j];
return true;
}
return false;
}
int main()
{
// __IN;__OUT;
RLL2(n ,m);
FOR(i,1,n) FOR(j,1,m) RLL(a[i][j]);
ll l = 0,r = 1e9;
while(l<=r)
{
ll x = (l+r)>>1;
if(check(x)) l = x+1;
else r = x-1;
}
PLN2(ansl,ansr);
return 0;
}