ARC081 C : Make a Rectangle(300)
作成日：2017.08.24
最終更新日：2017.08.24
問題概要
長さ$A_i$の棒が$N$本ある。
これらのうち異なるものを4本選び長方形を作る時、作ることのできる最大の長方形の面積を求めよ。
但し棒が長方形からはみ出してはならず、長方形が作れない場合は$0$を出力せよ。
制約
$4 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$
$A_i$は整数
考え方
長方形の向かい合う辺の長さは等しいから、同じ長さの棒を2本1組で考える。
求めるものは面積最大の長方形だから、組になった棒を長いものから2組選んで用いれば良い。
ソースコード
マクロ等はこちら
int N;
int A[102345];
int main(){
scanf("%d" , &N);
repp(i,0,N){
scanf("%d" , A + i);
}
sort(A,A+N,greater<int>());
LL x = 0, y = 0;
repp(i,1,N){
if(A[i-1] == A[i]){
if(x == 0){
x = A[i];
++i;
} else {
y = A[i];
break;
}
}
}
printf("%lld\n" , x * y);
return 0;
}解法まとめ
長い棒から2本1組にできるかを見て、組にできるものを2つ選ぶ。(9-22行)