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 = 1000000007;
long long a[1001000],b[1001000],cnt;
inline void work(){
      long long n,m,i,j,k;
      cnt=0;
      scanf("%lld",&n);
      for(i=1;i<=n;i++)
        scanf("%lld",&a[i]);
      sort(a+1,a+n+1);
      long long sum=0;
      for(i=1;i<=n;i++)
        if(!sum)sum++;
          else if(sum==1){
              if(a[i]==a[i-1]){
                b[++cnt]=a[i];
                sum=0;
              }
          }
      double ans=inf;
      long long x,y;
      for(i=1;i<cnt;i++)
        if(ans>double(b[i+1])/b[i]+double(b[i])/b[i+1]){
          ans=double(b[i+1])/b[i]+double(b[i])/b[i+1];
          x=b[i],y=b[i+1];
        }
      cout<<x<<' '<<x<<' '<<y<<' '<<y<<endl;
}
int main(){
      long long n,m,i,j,k,t;
      scanf("%lld",&t);
      while(t--){
          work();
      }
      return 0;
}