https://codeforces.com/contest/1529/problem/B
시간 1초, 메모리 256MB
input :
- t (1≤t≤104)
- n (1≤n≤105)
- a1, a2, …, an (−109 ≤ ai ≤ 109)
output :
- For each test case output a single integer — the length of the longest strange subsequence of
a.
각 테스트케이스의 정답을 출력하시오. 가장 긴 부분 문자열a의 길이를 출력하시오.
조건 :
- A sequence (b1, b2, …, bk) is called
strange, if the absolute difference between any pair of its elements is greater than or equal to the maximum element in the sequence.
배열의 모든 경우에 대해 어느 두 원소의 차의 절대값이 배열의 가장 큰 값보다 같거나 크면 이 배열을strange하다 한다.
어차피 부분문자열이기 때문에 순서도 상관없고 선정만 하면 된다.
일단 음수와 음수의 차의 절대값은 0보다 같거나 크다. 그렇기에 음수의 경우 언제나 포함 할 수 있다. 그렇다면 문제는 양수가 포함되는 경우이다.
아. 그리고 기억해야 하는 것이 어느 두 원소의 차를 구하는 경우에는 배열의 최대값도 물론 포함이 된다.
절대값의 차이가 가장 적은 경우를 생각해야 우리는 배열의 가장 큰 값보다 작은 경우가 존재하는 지 알 수 있다. 가장 적게 만드려면 어떻게 해야하는가??
정렬
입력받은 배열을 정렬한다. 이 때 원소 기준 좌우에 존재하는 대상에 대해 차의 절대값이 가장 작다. 그러니까 새로운 원소를 추가 할 때 prev에 위치하던 원소와의 차를 구하고 이 차이가 현재 추가하려는 원소보다 작은 경우 더 이상 원소를 추가하면 안 된다.
오름차순으로 정렬을 했기 때문에 새로 추가되는 원소는 언제나 현재 가지고 있는 배열에서 최대값이 되기 때문이다.
그리고 이 추가되는 원소만을 가지고는 모든 경우를 생각할 수 없다. 그렇기에 지금까지 계산한 것들의 차이를 계속 기록해야 하는데 이 중에서 필요한 것은 최소값이 필요하다. 이를 새로 추가하는 값과 비교하여 걸러내야 한다.
import sys
t = int(sys.stdin.readline())
for i in range(t):
n = int(sys.stdin.readline())
data = list(map(int, sys.stdin.readline().split()))
data.sort()
cnt = 1
prev = data[0]
diff = float('INF')
for j in range(1, len(data)):
temp = data[j]
if diff > abs(prev - temp):
diff = abs(prev - temp)
if diff >= temp:
cnt += 1
prev = temp
print(cnt)
