C. Minimum Value Rectangle

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--C. Minimum Value Rectangle

题解

中档题。题意大概是给出多个木棍,找出四个木棍组成矩形且满足周长平方除以面积最小。
经过计算得知(计算过程不写了),满足要求的必定是长度相邻的。所以排序依次判断比较即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + 5;

int q1, q2, pre, pre2;
long double minnum;
int input[maxn];
int t, n;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    for (cin >> t; t; t--) {
        minnum = 1ll << 60;
        pre = pre2 = 0;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> input[i];
        }
        sort(input + 1, input + n + 1);
        for (int i = 1; i <= n; i++) {
            if (pre == input[i]) {
                if (pre2 != 0) {
                    long double x(pre), y(pre2);
                    long double temp = (x + x + y + y)*(x + x + y + y) / (x*y);
                    if (temp < minnum) {
                        q1 = pre2;
                        q2 = pre;
                        minnum = temp;
                    }
                }
                pre2 = pre;
                pre = 0;
            }
            else {
                pre = input[i];
            }
        }
        cout << q1 << ' ' << q1 << ' ' << q2 << ' ' << q2 << endl;
    }
}

标签: greedy

添加新评论