입력으로 정수 변수 Number가 제공됩니다. 임의의 순서로 1에서 Number 범위의 요소를 포함하는 배열을 생각해 보겠습니다. 다음과 같은 배열에 대해 Number-1 작업을 수행하면
-
배열에서 두 개의 요소 A와 B를 선택합니다.
-
배열에서 A와 B 제거
-
A와 B의 제곱합을 배열에 더합니다.
결국에는 단일 정수 값을 얻게 됩니다. 목표는 해당 요소에 대해 가능한 최대값을 찾는 것입니다.
우선순위 대기열 사용
-
최종 결과를 최대화하려면 A와 B가 최대가 되도록 선택해야 합니다.
-
최대 A와 B를 찾기 위해 우선 순위 대기열을 사용하여 그 안에 요소 값을 저장합니다.
-
우선순위 큐는 요소를 내림차순으로 저장합니다.
-
최상위 요소는 값이 가장 큽니다. 따라서 두 요소를 팝한 후 해당 사각형을 다시 대기열로 푸시합니다.
-
원하는 결과를 얻으려면 숫자 - 1번을 누르고 누릅니다.
예시
입력 − 숫자=2
출력 − 배열 축소 후 단일 요소:5
설명 − 배열에 [ 1 2]
와 같은 요소가 있다고 가정합니다.Priority Queue에 삽입 후-:2 1
A=5, B=4 :A 2 +B 2 =1+4=5
마지막 요소:5
입력 - 숫자=5
출력 − 배열 축소 후 단일 요소:5
설명 − 배열에 [ 5 1 2 4 3]
요소가 있다고 가정합니다.Priority Queue에 삽입 후-:5 4 3 2 1
A=5, B=4 :A 2 +B 2 =25+16=41 :41 3 2 1
A=41, B=3 :A 2 +B 2 =1681+9=1690 :1690 2 1
A=1690, B=2 :A 2 +B 2 =1681+4=2856104 :2856104 1
A=2856104 , B=1 :A 2 +B 2 =1187163712+1=1187163713 :1187163713
마지막 요소 :1187163713
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
이 접근 방식에서 우리는 배열의 요소를 내림차순으로 저장하기 위해 대기열의 우선 순위를 지정할 것입니다. 상위 두 개의 가장 큰 요소를 팝하고 두 요소의 제곱합을 해당 대기열에 다시 푸시합니다. 값이 하나만 남을 때까지 이 작업을 수행합니다.
-
입력 변수 번호를 가져옵니다.
-
결과에 대한 데이터 유형을 긴 정수로 사용 - lli
-
reduceArray(int Num) 함수는 입력된 숫자를 취하고 위의 연산을 사용하여 계산된 최대 단일 정수를 반환합니다.
-
우선순위 큐를 pQueue로 가져옵니다.
-
while 루프를 사용하여 1에서 N까지의 숫자로 pQueue를 채웁니다.
-
i<=Num 동안 i를 pQueue로 푸시
-
이제 pQueue는 1에서 N까지의 정수를 내림차순으로 가지며 크기는 N입니다.
-
이제 크기가>=1이 될 때까지 while 루프를 사용하여 pQueue를 순회합니다.
-
최대값을 var1=pQueue.top()으로 가져와서 팝니다.
-
다음 최대값을 var2=pQueue.top()으로 가져와서 팝니다.
-
var1을 정사각형으로 설정하고 var2를 정사각형으로 설정합니다.
-
var1+var2를 pQueue에 다시 푸시합니다.
-
while 루프가 끝나면 맨 위 요소를 반환합니다.
-
메인 안에 결과를 출력하세요.
예시
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int reduceArray(int Num){
priority_queue<lli> pQueue;
int i=1;
while(i<=Num){
pQueue.push(i);
i=i+1;
}
while (pQueue.size() > 1) {
lli var1 = pQueue.top();
pQueue.pop();
lli var2 = pQueue.top();
pQueue.pop();
var1=var1*var1;
var2=var2*var2;
pQueue.push(var1+var2);
}
return pQueue.top();
}
int main(){
int Number = 5;
cout<<"Single element after array reduction: "<<reduceArray(Number);
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Single element after array reduction: 1187163713