当前位置: 代码迷 >> 综合 >> codeforces ECR 80 minimax problem (二分 构造)
  详细解决方案

codeforces ECR 80 minimax problem (二分 构造)

热度:60   发布时间:2024-01-25 11:29:28.0

题目大意:

有n个数列,选出第i,j个,我们可以得到新数列如下:

for k 1->m:

    a[z][k]=max(a[i][k],a[j][k])

问我们得到的新数列z中,哪一个的min(a[z][k])最大 即:

max(min (a[z][k])))  {k:1->m }

解题思路:

这种最小值最大 或者 最大值最小一般都是用二分来做。我们直接枚举答案mid,同时每次枚举时原数列中大于等于mid的置1。若它们中的任意两个的按位或等于2^m-1,那么我们认为是true 把答案往右偏。注意两两枚举数列的复杂度位n^2,但是注意到这里的m只为8,所以复杂度可以压缩到2^8,把相同的合并即可。

第一个问题:为什么可以用二分?因为这里满足 true true true false false结构,我们需要求出最后一个true的位置。

第二个问题:为什么想到这样构造:其实这样构造是蛮常见的技巧。即把数列中某个大于x的值全置为1,其它全置为0.

n,m=[int(i) for i in input().split(" ")]
arrmv=[]
for i in range(n):arrmv.append([int(i) for i in input().split(" ")])
x=0
y=int(1e9+1)
sucls=[0,0]
tols=[]
powls=[int(pow(2,i)) for i in range(10)]
twodarray=[0  for i in range(257)]
while x+1<y:mid = x+(y-x)//2for idx,ele in enumerate(twodarray):twodarray[idx]=0tols.clear()for topidx, eletop in enumerate(arrmv):tmp=0for idx,ele in enumerate(eletop):if ele>=mid:tmp+=powls[idx]if not twodarray[tmp]:twodarray[tmp]=1tols.append((tmp,topidx))sz=len(tols)suc=0no=int(pow(2,m))for i in range(sz):for j in range(i,sz):if tols[i][0] | tols[j][0] == no-1:sucls[0],sucls[1]=tols[i][1],tols[j][1]suc=1;break;if suc:breakif suc:x=midelse:y=midprint(sucls[0]+1,sucls[1]+1)

 

  相关解决方案