CodeForces 1027C-Minimum Value Rectangle

小咪咪 2022-05-15 12:06 124阅读 0赞

*  # CodeForces 1027C-Minimum Value Rectangle #

--------------------

*  ## 题目链接： ##

### [C. Minimum Value Rectangle][] ###

*  ## 思路： ##

### 题目大意： ###

给定n条边，选出4根构造长方形，周长P=2\*（x+y） 面积S=xy,求出比值 P/S 最小的长方形组合（有多答案，输出一个）

### 题解： ###

化简了一下

**P/S = x/y + y/x**  ，可得x y 越接近，P/S就越小，那么将能作为长方形的边排序，则只有两边相邻才有可能构造长方形

**首先就是挑出成对存在的边，将相等边数值进优先队列，然后相邻比较，记录最小情况的两条边**

### 坑： ###

精度很高，直到很高，差值进度在 1e-12 附近

*  ## 代码： ##

#include<iostream>
    #include<algorithm>
    #include<memory.h>
    #include<cstdio>
    #include<queue>
    #include<vector>
    using namespace std;
    bool Vis[10005];
    
    int main()
    {
        int n,T;
        int Length;
        cin>>T;
        while(T--)
        {
            priority_queue<int,vector<int>,greater<int> > Sticks;
            memset(Vis,0,sizeof(Vis));
            cin>>n;
            for(int i=1;i<=n;i++)
            {
                scanf("%d",&Length);
                if(Vis[Length])   
                {
                    Sticks.push(Length); 
                    Vis[Length]=false;
                }
                else
                    Vis[Length]=true;//true表示单数存在
            }
            int Res1,Res2;
            double Min=10000000.0;
            while(!Sticks.empty())
            {
                int a=Sticks.top();
                Sticks.pop();
                if(Sticks.empty())
                    break;
                int b=Sticks.top();
                Sticks.pop();
                //cout<<a<<" "<<b<<endl;
                double c=((a*a+b*b)*1.0)/(a*b*1.0);
                if(Min-c>1e-12)
                {
                    Min=c;
                    Res1=a;
                    Res2=b;
                }
                Sticks.push(b);   //重新入队
            }
            cout<<Res1<<" "<<Res1<<" "<<Res2<<" "<<Res2<<endl;
        }
        return 0;
    }

[C. Minimum Value Rectangle]: http://codeforces.com/problemset/problem/1027/C