CodeForces 1027C-Minimum Value Rectangle

小咪咪 2022-05-15 12:06 189阅读 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

    include

    include

    include

    include

    include

    using namespace std;
    bool Vis[10005];

    int main()
    {

    1. int n,T;
    2. int Length;
    3. cin>>T;
    4. while(T--)
    5. {
    6.     priority_queue<int,vector<int>,greater<int> > Sticks;
    7.     memset(Vis,0,sizeof(Vis));
    8.     cin>>n;
    9.     for(int i=1;i<=n;i++)
    10.     {
    11.         scanf("%d",&Length);
    12.         if(Vis[Length])   
    13.         {
    14.             Sticks.push(Length); 
    15.             Vis[Length]=false;
    16.         }
    17.         else
    18.             Vis[Length]=true;//true表示单数存在
    19.     }
    20.     int Res1,Res2;
    21.     double Min=10000000.0;
    22.     while(!Sticks.empty())
    23.     {
    24.         int a=Sticks.top();
    25.         Sticks.pop();
    26.         if(Sticks.empty())
    27.             break;
    28.         int b=Sticks.top();
    29.         Sticks.pop();
    30.         //cout<<a<<" "<<b<<endl;
    31.         double c=((a*a+b*b)*1.0)/(a*b*1.0);
    32.         if(Min-c>1e-12)
    33.         {
    34.             Min=c;
    35.             Res1=a;
    36.             Res2=b;
    37.         }
    38.         Sticks.push(b);   //重新入队
    39.     }
    40.     cout<<Res1<<" "<<Res1<<" "<<Res2<<" "<<Res2<<endl;
    41. }
    42. return 0;

    }

发表评论

表情：
评论列表 （有 0 条评论，189人围观）

还没有评论，来说两句吧...

相关阅读