CF1619D.New Year‘s Problem

CF1619D.New Year’s Problem

• 贪心

• 因为只能取到n-1个商店，因此当n-1 > m时一定会有两人在同一家商店买礼物

  • 枚举哪一家商店，哪两个人买礼物，再与最优时候(不管n-1)的最小值取小
  • 代码附注释如下

•   #include<bits/stdc++.h>
    
    using namespace std;
    const int N = 100010;
    int T,n,m;
    
    int main()
    {
        cin>>T;
        while(T --)
        {
            cin>>m>>n;
            //mins为所有礼物最大满意度的最小值
            int ans = 0,min_s = INT_MAX;
            //存礼物的满意度
            vector<vector<int>> p(m,vector<int>(n));
            //存每种礼物的最大满意度
            vector<int> max_s(n);
            
            for(int i=0;i<m;i++)
                for(int j=0;j<n;j++)
                {
                    int x;
                    cin>>x;
                    //同种礼物取最大
                    max_s[j] = max(max_s[j],x);
                    p[i][j] = x;
                }
                
            //所有种礼物的最大心意中的最小
            for(int i=0;i<n;i++)
                min_s = min(min_s,max_s[i]);
            
            //说明想在哪买在哪买,直接就是min_s为答案
            if(n - 1 >= m) 
                ans = min_s;
            else
            {
                //枚举商店
                for(int k=0;k<m;k++)
                    //双指针枚举两个人
                    for(int i=0;i<n;i++)
                        for(int j=i+1;j<n;j++)
                            //ans为最大的结果
                            //当前商店买这两种礼物与之前最小再取最小为当前情况结果
                            ans = max(ans,min({min_s,p[k][i],p[k][j]}));
            }
            cout<<ans<<endl;
        }
        return 0;
    }