Educational Codeforces Round 49(Rated for Div.2) #C Minimum Value Rectangle 문제풀이입니다.
문제링크입니다.
http://codeforces.com/contest/1027/problem/C
Problem Solving Strategy
수학 문제입니다.
문자로 나타내어 식을 열심히 변형하면 결론은 a/b+b/a가 최소가 될 때 각각의 a, b를 구하는 문제와 동치입니다.
그래프를 그려보면, 사실 a, b각각의 값이 중요한게 아니고, 비율이 중요하죠.
b>a라고 했을 때 a/b가 1에 가까울수록 a/b+b/a가 최소가 되겠죠.
코딩 전략
n이 10^6이라는 좀 큰 범위긴 하다만,
사실 an의 범위 해당하는 1부터 10^4까지의 숫자가 2번 나타나는지 4번 나타나는지가 중요합니다.
따라서 배열 크기는 10^4로 잡아줍니다.
입력받으면서 1~10000까지의 숫자가 각각 몇 번 나타나는지 기록하는데,
2번 나타날 때거나 4번 나타날 때, b라는 새로운 배열을 만들어서, 기록합니다.
4번 이상 나타난 수는 두 번 기록되고, 2-3회 등장한 수는 한 번 기록되겠죠.
b라는 배열을 정렬합니다. 왜? 비율이 최소가 되는게 궁금하니까, 인접해있는 수만 비교하면 됩니다.
예를 들어 1, 2, 8, 11 세 숫자 중 비율이 최소가 되는 두 수를 고르려면
1과 2 / 2와 8 / 8과 11 이 세 경우만 비교하면 되겠죠?
열심히 비교해서 최소가 되는 경우 체크한 뒤, 나중에 출력합니다.
틀리는 경우
시간 초과 나는 경우에 대해 생각해보자면,
(사실 제가 걸린 거)
코딩 편하게 하려고
b배열을 잡지 않고, 그냥 a배열을 훑으면서 풀려고 하다가,,,
n=6으로 T가 왕창 많이 들어왔을 경우 O(10000*T)>2~3초로 가볍게 넘어가버렸습니다...;;;
전체 코드 보기
|
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
|
#include<bits/stdc++.h>
using namespace std;
//a는 입력배열, b는 두 번 이상 나타나는 수들 목록
int T,n,a[10004],b[10004],ipt,take1,take2,bsz; double ans;
int main(){
scanf("%d",&T);
while(T--){
scanf("%d",&n);
keep=0, ans=0, bsz=0; for(int i=0;i<=10002;i++) a[i]=0;
for(int i=1;i<=n;i++){
scanf("%d",&ipt);
a[ipt]++;
if(a[ipt]==2||a[ipt]==4) b[bsz]=ipt, bsz++;
}
sort(b,b+bsz);
for(int i=1;i<bsz;i++){
if(ans<(double)b[i-1]/(double)b[i]){
ans=(double)b[i-1]/(double)b[i];
take1=b[i-1]; take2=b[i];
}
}
printf("%d %d %d %d\n",take1,take1,take2,take2);
}
}
|
cs |