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;}