专栏首页一Wa哇一天D. Minimax Problem

D. Minimax Problem

题目链接:D. Minimax Problem

time limit per test:5 seconds memory limit per test:512 megabytes inputstandard input outputstandard output

You are given n arrays a1, a2, …, an; each array consists of exactly m integers. We denote the y-th element of the x-th array as ax,y.

You have to choose two arrays ai and aj(1≤i,j≤n, it is possible that i=j). After that, you will obtain a new array b consisting of m integers, such that for every k∈[1,m] bk=max(ai,k,aj,k).

Your goal is to choose i and j so that the value of $\sum_{k=1}^m$bk is maximum possible.

Input The first line contains two integers n and m (1≤n≤3⋅105, 1≤m≤8) — the number of arrays and the number of elements in each array, respectively.

Then n lines follow, the x-th line contains the array ax represented by m integers ax,1, ax,2, …, ax,m (0≤ax,y≤10^9^).

Output Print two integers i and j (1≤i,j≤n, it is possible that i=j) — the indices of the two arrays you have to choose so that the value of $\sum_{k=1}^m$bk is maximum possible. If there are multiple answers, print any of them.

Example input

6 5
5 0 3 1 2
1 8 9 1 3
1 2 3 4 5
9 1 0 3 7
2 3 0 6 3
6 4 1 7 0

output

1 5

题目大意

给你两个数,n和m,表示n个数组每个数组有m个元素,然后让你输出任意两个数组合并后数组中的最小值最大是几,合并的规则是两个数组的同一个位置取最大值,比如:1 2 3 4 5 和 5 4 3 2 1这两个数列合并后的值为 5 4 3 4 5;最小值时3;

解题思路

既然是求最小值最大,那么很容易想到二分,但是我们该如何check呢?当行很大,列很小的时候很容易想到状压,但是如何表示状态呢?,既然是两个数列合并后的最小值都要大于二分的 mid,所以用二进制来表示每个数列满足要求的状态,比如说一共4个数 现在需要合并后的值大于等于3 两个数列是 1 3 4 1 那么这个数列满足大于等于3的值可以用6表示(第2位和第3位大于等于三,也就是二进制的第二位和第三位唯一,结果是6)另一个是4 1 3 4 状态表示为11,然后6|11等于列数4所以可以,如果不等那就不成立,现在我们check和二分都有了,就可以码代码了。

代码

#include<bits/stdc++.h>
using namespace std;
int a[500000][10];//存图 
int ans[1000];//判断这个状态是否成立 
int ans_pos[1000];//表示这个成立这个状态是第几行 
int n,m;
int ans1,ans2;//记录成立的两个状态 
bool check(int x)
{
    int t;
    memset(ans,0,sizeof ans);//每次初始化状态数组 
    for(int i=1;i<=n;i++)
    {
        t=0;//记录状态 
        for(int j=0;j<m;j++)
        {                            //这里的 位运算 | 简化了相互的加法,不懂得自己模拟一遍 
            if(a[i][j]>=x) t|=(1<<j);// j的第几个元素满足情况,第几位为 1 
        }
        ans[t]=1;//这个状态存在,就唯一; 
        ans_pos[t]=i;//记录这个状态是第几行; 
    }
    int k=1<<m;//一共 m 列如果都是 1 那么 二进制就是 m 个1 
    for(int i=0;i<k;i++)
    {
        if(!ans[i]) continue;//如果这个状态为0,说明不存在 
        for(int j=0;j<k;j++)
        {
            if(!ans[j]) continue;
            if((i|j)==k-1)//如果 两个位置 或 后等于k,那么说明情况合法 
            {
                ans1=ans_pos[i];//ans1 ans2 满足此状态的两行行数 
                ans2=ans_pos[j];// 
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        cin>>a[i][j];
    }
    int l=0,r=0x3f3f3f3f;
    int mid;
    while(l<=r)//二分模板写法 
    {
        mid=(l+r)/2;
        if(check(mid)) l=mid+1;
        else r=mid-1;
    }
    cout<<ans1<<" "<<ans2<<'\n';
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 并查集

    POJ 的题真的是对小白选手的一个大的磨炼了,看了好久才明白题意,然后发现还是不会写题意就是给你一个数n,然后又n次操作,每次操作有两种情况如果第一个字符是 M...

    某些人
  • 2019-2020 ICPC Southeastern European Regional Programming Contest (SEERC 2019)-G.Projection

    Everybody knows that you are a TensorFlow fan. Therefore, you’ve been challenged...

    某些人
  • POJ-2585-Window Pains

    Window PainsTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 2915 ...

    某些人
  • CodeForces 666B World Tour(spfa+枚举)

    B. World Tour time limit per test 5 seconds memory limit per test 512 mega...

    ShenduCC
  • poj-------(2240)Arbitrage(最短路)

    Arbitrage Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 156...

    Gxjun
  • HDU 3032 Nim or not Nim?(Multi-Nim)

    Problem Description Nim is a two-player mathematic game of strategy in which ...

    attack
  • 【Codeforces】1213B - Bad Prices

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • POJ 2594 Treasure Exploration

    Description Have you ever read any book about treasure exploration? Have you ev...

    attack
  • LeetCode Weekly Contest 28解题思路

    好吧,不要被这道题的例子给骗了。要求输出的最大,意思就是求除第一个元素之外的其他division最小,而不断连除就是第二部分的最小值,所以有如下代码:

    用户1147447
  • Codeforces 626E Simple Skewness(暴力枚举+二分)

    E. Simple Skewness time limit per test:3 seconds memory limit per test:256 megab...

    Angel_Kitty

扫码关注云+社区

领取腾讯云代金券