「Codeforces 1027C」Minimum Value Rectangle

发表于 | | 阅读次数:
字数统计: 515 字

Description

题目链接：Codeforces 1027C

给出 $n$ 条线段，在其中选择 $4$ 条线段组成一个矩形，记 $P$ 为围成的矩形的周长，$S$ 为围成的矩形的面积，求使得 $\frac{P^2}{S}$ 最小的 $4$ 条线段。

本题 $T$ 组数据。

数据范围：$1\le T\le 10^6$，$4\le\sum n\le 10^6$，$1\le a_i\le 10^4$

Solution

设 $4$ 条线段为 $a,a,b,b\ (a\le b)$，则有 $P=2\cdot(a+b)$，$S=ab$，可得

因此我们只需要最小化 $\frac{b}{a}$ 即可（千万注意此处 $a\le b$）。

分类讨论

  1. 如果有 $4$ 条相等的线段，肯定选取这 $4$ 条。
  2. 否则将数量不小于 $2$ 的线段从小到大排序，贪心选择相邻的线段。将当前的 $a’,b’$ 和已知的较优解 $a,b$ 比较得出更优解。

注意精度问题！我们可以将判定条件 $\frac{b’}{a’}<\frac{b}{a}$ 转化为 $ab’<a’b$ 即可防止精度问题。

时间复杂度：$O(Tn\log a_i)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <cstdio>
#include <cctype>
#include <map>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
inline char in() {
    static char buf[10001],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++;
}
template <class Tp> void read(register Tp &s) {
    s=0;
    register bool neg=0;
    register char c;
    while(!isdigit(c=in())) if(c=='-') neg=1;
    while(s=(s<<3)+(s<<1)+c-48,isdigit(c=in()));
    s=(neg?-s:s);
}

int T,n,a[1000005];
std::map<int,int> cnt;
int main() {
    for(read(T);T;--T) {
        cnt.clear();
        read(n);
        int t,m=0;
        FOR(i,1,n) read(t),cnt[t]++;
        bool flg=0;
        for(std::map<int,int>::iterator it=cnt.begin();it!=cnt.end();++it) {
            if((*it).second>=2) a[++m]=(*it).first;
            if((*it).second>=4) {
                flg=1;
                int ans=(*it).first;
                printf("%d %d %d %d\n",ans,ans,ans,ans);
                break;
            }
        }
        if(flg) continue;
        int x=a[1],y=a[2];
        FOR(i,3,m) if(x*a[i]<a[i-1]*y) x=a[i-1],y=a[i];
        printf("%d %d %d %d\n",x,x,y,y);
    }
    return 0;
}
0%