CF1027C Minimum Value Rectangle【贪心/公式化简】

https://www.luogu.org/problemnew/show/CF1027C

#include<cstdio>

#include<string>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<cstring>

#include<set>

#include<queue>

#include<algorithm>

#include<vector>

#include<map>

#include<cctype>

#include<stack>

#include<sstream>

#include<list>

#include<assert.h>

#include<bitset>

#include<numeric>

#define debug() puts("++++")

#define gcd(a,b) __gcd(a,b)

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define fi first

#define se second

#define pb push_back

#define sqr(x) ((x)*(x))

#define ms(a,b) memset(a,b,sizeof(a))

#define sz size()

#define be begin()

#define pu push_up

#define pd push_down

#define cl clear()

#define lowbit(x) -x&x

#define all 1,n,1

#define mod(x) ((x)%M)

#define pi acos(-1.0)

#define rep(i,x,n) for(int i=(x); i<(n); i++)

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

typedef pair<int,int> P;

const int INF = 0x3f3f3f3f;

const int maxn = 1e4+10; //1e5不行！

const double eps = 1e-8;

const int dx[] = {-1,1,0,0,1,1,-1,-1};

const int dy[] = {0,0,1,-1,1,-1,1,-1};

int dir[2]={-1,1};

const int mon[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

const int monn[] = {0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int t,n;

int vis[maxn];

int b[maxn];

int x;

inline int read() //要读入挂！

{

    char x;

    while((x = getchar())<'0' || x>'9');

    int u = x-'0';

    while((x = getchar())>='0' && x<='9') u = (u<<3)+(u<<1)+x-'0';

    return u;

}

/*

1345 4409 1345 4409 8664 8664

4409 4409 8664 8664=4225(v)

1345 1345 4409 4409=3064(x)

*/

int main()

{

    t=read();

    while(t--)

    {

        int f=1;

        ms(vis,0);

        ms(b,0);

        n=read();

        int m=0;

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

        {

            x=read();

            vis[x]++;

            if(vis[x]==4 && f)

            {

                printf("%d %d %d %d\n",x,x,x,x);

                f=0;

            }

            if(vis[x]==2 && f)

                b[m++]=x;

        }

        if(f)

        {

            sort(b,b+m);

            int l,r;

            double Min=INF;

            for(int i=0;i<m-1;i++)

            {

                double tmp = (double)b[i]/b[i+1]+(double)b[i+1]/b[i];

                if(tmp<Min)

                {

                    Min = tmp;

                    l=b[i];

                    r=b[i+1];

                }

            }

            printf("%d %d %d %d\n",l,l,r,r);

        }

    }

    return 0;

}

/*

【题意】

3

4

7 2 2 7

8

2 8 1 4 8 2 1 5

5

5 5 5 5 5

【类型】

【分析】

【时间复杂度&&优化】

【trick】

【数据】

*/