1027C Minimum Value Rectangle

传送门

题目大意

有n个木棍，让你选4根使得组成的矩形的周长的平方除以面积最小。

分析

这个题看起来就是一个需要证明的贪心，下面我们来证明一下：

所以我们只需要枚举一边所有的a的可能值，然后b就是比a大的边中最小的，复杂度O(n)。总复杂度O(nlogn)。

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<cctype>

#include<cmath>

#include<cstdlib>

#include<queue>

#include<ctime>

#include<vector>

#include<set>

#include<map>

#include<stack>

using namespace std;

const double inf = ;

long long a[],b[],cnt;

inline void work(){

      long long n,m,i,j,k;

      cnt=;

      scanf("%lld",&n);

      for(i=;i<=n;i++)

        scanf("%lld",&a[i]);

      sort(a+,a+n+);

      long long sum=;

      for(i=;i<=n;i++)

        if(!sum)sum++;

          else if(sum==){

              if(a[i]==a[i-]){

                b[++cnt]=a[i];

                sum=;

              }

          }

      double ans=inf;

      long long x,y;

      for(i=;i<cnt;i++)

        if(ans>double(b[i+])/b[i]+double(b[i])/b[i+]){

          ans=double(b[i+])/b[i]+double(b[i])/b[i+];

          x=b[i],y=b[i+];

        }

      cout<<x<<' '<<x<<' '<<y<<' '<<y<<endl;

}

int main(){

      long long n,m,i,j,k,t;

      scanf("%lld",&t);

      while(t--){

          work();

      }

      return ;

}