codeforces 1288 D 二分+二进制check
程序员文章站
2022-04-04 20:04:49
...
题目链接:https://codeforces.com/contest/1288/problem/D
题目大意:
二分一个最小值。考虑check。
我们去原数组,如果a[i][j]>=mid。为1,否则为0。那么把每一行压缩成一个二进制数。放入桶中。再去桶里枚举i, j。如果i|j=(1<<m)-1说明满足这个最小值。
#include <bits/stdc++.h>
#define LL long long
using namespace std;
int a[300005][10];
int b[300005];
int n, m, x, y;
int check(int mid){
int c[1024]={0};
for(int i=1; i<=n; i++){
int t=0;
for(int j=1; j<=m; j++){
if(a[i][j]>=mid){
t+=(1<<(j-1));
}
}
c[t]=i;
}
for(int i=0; i<(1<<m); i++){
for(int j=0; j<(1<<m); j++){
if(c[i]&&c[j]&&(i|j)==(1<<m)-1){
x=c[i], y=c[j];
return 1;
}
}
}
return 0;
}
int main(){
int ansx, ansy;
scanf("%d%d", &n, &m);
for(int i=1; i<=n; i++){
for(int j=1; j<=m; j++){
scanf("%d", &a[i][j]);
}
}
int L=0, R=1e9;
while(L<=R){
int mid=(L+R)/2;
if(check(mid)){
L=mid+1;
ansx=x, ansy=y;
}
else{
R=mid-1;
}
}
printf("%d %d\n", ansx, ansy);
return 0;
}
上一篇: jQuery运行页面怎样默认触发点击事件
下一篇: Java方法返回多种类型
推荐阅读
-
Magazine Ad CodeForces - 803D(二分 + 贪心,第一次写博客)
-
Codeforces Round #256 (Div. 2)D 二分答案_html/css_WEB-ITnose
-
CodeForces - 1088D Ehab and another another xor problem (构造,二进制,交互)
-
D. Cutting Out (二分查找) Codeforces Round #521 (Div. 3)
-
Codeforces Round #220 (Div. 2) D 树状数组 && 二分_html/css_WEB-ITnose
-
codeforces 514d R2D2 and Droid Army (RMQ+二分)
-
codeforces 1288 D 二分+二进制check
-
Magazine Ad CodeForces - 803D(二分 + 贪心,第一次写博客)