배열이 a[n]
있습니다. 번호 n
는 우리에 의해 입력됩니다. 다음 a[i]
과 같은 a[j]
경우 의 최소 제품을 찾아야합니다 .
1) abs(i - j) > k
2) a[i] * a[j]
최소화
여기 내 해결책이 있습니다 (매우 순진합니다).
#include <iostream>
using namespace std;
#define ll long long
int main() {
ll n,k; cin >> n >> k;
ll a[n]; for(ll i=0;i<n;i++) cin >> a[i];
ll mn; bool first = true;
for(ll i=0;i<n;i++) {
for(ll j=0;j<n;j++) {
if(i!=j)
if(abs(i-j) > k) {
if(first) {
mn = a[i]*a[j];
first = false;
} else if(a[i]*a[j] < mn) mn = a[i]*a[j];
}
}
}
cout << mn << endl;
}
그러나 거리가 작은 최소 제품을 찾는 더 빠른 방법이 있는지 알고 싶습니다.
답변
조건을 만족하는 요소 쌍이 하나 이상 있고 두 요소의 곱셈이 오버플로되지 않는다고 가정하면 Theta(n-k)
시간과 Theta(1)
공간에서 최악의 상황과 최상의 경우에 다음과 같이 수행 할 수 있습니다 .
auto back_max = a[0];
auto back_min = a[0];
auto best = a[0]*a[k+1];
for(std::size_t i=1; i<n-(k+1); ++i) {
back_max = std::max(back_max, a[i]);
back_min = std::min(back_min, a[i]);
best = std::min(best, std::min(a[i+k+1]*back_max, a[i+k+1]*back_min));
}
return best;
이것은 최적의 곱이 적어도 거리에 a[0]
있는 임의의 n-(k+1)
요소 와 함께 있을 수 k+1
있으므로 n-(k+1)
문제를 해결하는 알고리즘에 의해 정수를 읽을 필요가 있기 때문에 시간과 공간 모두에 대한 점근 적 최악의 복잡성 측면에서 최적 입니다.
알고리즘의 기본 개념은 다음과 같습니다.
최적의 제품은 두 가지 요소를 사용 a
, 이것들이 있다고 가정 a[r]
하고 a[s]
. 일반성을 잃지 않고 우리는 s > r
제품이 정식이기 때문에 가정 할 수 있습니다 .
제한 사항으로 인해 abs(s-r) > k
이는 다음을 의미합니다 s >= k+1
. 이제이 s
조건을 만족하는 각 인덱스가 될 수 있으므로이 인덱스를 반복합니다. 그것은 i
표시된 코드에서 반복 이지만 k+1
편의를 위해 변경됩니다 (실제로 중요하지는 않습니다). 각 반복에 대해 i+k+1
가장 큰 지수를 포함하는 최적의 제품을 찾아 이전의 최고 추측과 비교해야합니다.
페어링 할 수있는 인덱스 는 거리 요구 사항으로 인해 i+k+1
모든 인덱스가 작거나 같습니다 i
. 우리는 이들 모두를 반복해야하지만 고정에서 최소 a[i+k+1]*a[j]
이상 은 제품의 단 조성으로 인해 동일하기 때문에 불필요 합니다 (최소 및 최대 초과 모두에 대해 최소를 취하면 가능한 두 가지를 설명합니다) 단조의 두 가지 가능한 방향의 표시 또는 동등하게.)j
i
min(a[i+k+1]*max(a[j]), a[i+k+1]*min(a[j]))
a[j]
a[i+k+1]
집합 이후 a[j]
어떤 값 이상 방금 여기 최적화 {a[0], ..., a[i]}
단순히 하나 개의 원소 (의해 성장되는 a[i]
각 반복에서) i
, 우리는 단순히 추적 유지할 수 max(a[j])
및 min(a[j])
경우이를 갱신하여 단일 변수를 a[i]
이전의 최적 값보다 더 크거나 작아진다. 이 이루어집니다 back_max
및 back_min
코드 예제에.
반복의 첫 번째 단계 ( i=0
)는 루프에서 건너 뛰고 대신 변수 초기화로 수행됩니다.
답변
가장 빠른 확실하지 않습니다 .
i <j-k 가없는 간단한 문제의 경우, 최소 곱은 가장 작고 큰 두 요소의 쌍 곱입니다.
따라서 (다음은 너무 복잡합니다. 호두의 대답 참조 )
(• k ≤ n 인 경우 balk
• minProduct를 a [0] * a [k + 1]으로 초기화)
-
{} 및 {a [ j ]로 시작하여 두 개의 동적 minmax 데이터 구조를 upToI 및 beyondIplusK 이상으로 유지 k ≤ j }
- 각각의 i 에 대해 0 내지 n – k -1
- upToI에 [ i ]를 추가하십시오
- beyondIplusK 에서 a [ i + k ]를 제거합니다
-
min ( upToI ) × min ( beyondIplusK ), min ( upToI ) × max ( beyondIplusK ),
max ( upToI ) × min ( beyondIplusK ) 및 max ( upToI ) × max ( beyondIplusK ) 중에서 새로운 최소 제품 확인
답변
“최소 크기”
2 개의 “가장 작은 크기”요소를 찾은 다음 (두 개의 0을 찾거나 전체 배열을 검색 한 후) 곱하십시오.
abs(i - j) > k
부품이 없는 “가장 낮은 값”
3 가지 가능성이 있습니다 :
-
두 개의 가장 높은 (가장 작은) 음수
-
음수가 아닌 두 개의 가장 작은 (가장 작은) 숫자
-
가장 작은 (가장 큰 크기) 음수 및 가장 큰 (가장 큰 크기) 음수가 아닌 숫자
6 개의 값을 모두 검색하고 제품을 파악할 수 있으며 최종적으로 가장 적합한 제품을 찾을 수 있습니다.
하나; 0을 보자 마자 처음 두 가지 가능성에 대해 더 이상 알 필요가 없습니다. 음수 하나와 음수가 아닌 숫자가 보이면 세 번째 가능성에만 관심이 있다는 것을 알게됩니다.
이는 “모든 3 가지 가능성에 대한 관심”, “음수가 보이지 않는 한 답은 0″및 “마지막 가능성에 대한 관심”이라는 3 가지 상태의 유한 상태 머신으로 이어집니다. 이것은 3 개의 루프 세트로 구현 될 수 있으며, 여기서 goto
유한 상태 머신의 상태가 변경 될 때 루프 중 2 개가 다른 루프의 중간으로 점프 합니다.
특히, (모호하지 않은) 것과 같이 모호하게 보일 수 있습니다.
// It could be any possibility
for(ll i=0;i<n;i++) {
if(a[i] >= 0) {
if(a[i] < lowestNonNegative1) {
lowestNonNegative2 = lowestNonNegative1;
lowestNonNegative1 = a[i];
}
if(lowestNonNegative2 == 0) {
goto state2;
}
} else {
if(a[i] > highestNegative1) {
highestNegative2 = highestNegative1;
highestNegative1= a[i];
}
if(lowestNonNegative1 < LONG_MAX) {
goto state3;
}
}
}
if(lowestNonNegative2 * lowestNonNegative1 < highestNegative2 * highestNegative1) {
cout << lowestNonNegative2 * lowestNonNegative1;
} else {
cout << highestNegative2 * highestNegative1;
}
return;
// It will be zero, or a negative and a non-negative
for(ll i=0;i<n;i++) {
state2:
if(a[i] < 0) {
goto state3;
}
}
cout << "0";
return;
// It will be a negative and a non-negative
for(ll i=0;i<n;i++) {
state3:
if(a[i] < lowestNegative) {
lowestNegative = a[i];
} else if(a[i] > highestNonNegative) {
highestNonNegative = a[i];
}
}
cout << lowestNegative * highestNonNegative;
return;
abs(i - j) > k
부품 이있는 “가장 낮은 값”
이 경우 여전히 3 가지 가능성이 있습니다. 동일한 “유한 상태 머신의 3 루프”접근 방식으로 작동하게 만들 수 있지만 너무 지저분합니다. 이 경우 더 나은 대안은 배열이 사전 스캔되어 0이 있는지, 모두 음인지 또는 양수인지를 판별하는 것입니다. 사전 스캔 후 응답이 0임을 알 수 있거나 특정 가능성만으로 설계된 루프를 선택할 수 있습니다.