[白俊C+]1026宝物
質問する
むかしむかし、数学はいつも面倒だった国がありました.この国の王金智敏は以下の問題を起こして、大金を懸賞した.
長さNの整数配列AとBがある.定義関数S:
S = A[0] × B[0] + ... + A[N-1] × B[N-1]
Sの値を最小にするために、Aの数を並べ替えます.ただし、Bの数は並べ替えることはできません.
プログラムを作成して、Sの最大値を出力してください.
入力
1行目はNです.2行目はAのN個、3行目はBの数である.Nは50以下の自然数であり、AおよびBの各要素は100以下の整数ではない.
しゅつりょく
1行目はSの最大値を出力する.
https://www.acmicpc.net/problem/1026
に答える
アルゴリズム分類から見ると,グレディアルゴリズムが用いられ,いずれにしても,各選択は最適な選択を行うアルゴリズムである.
まず、問題ルールは、最大のB要素と最小のA要素を乗算することを要求する.
A配列を整理するために,階調アルゴリズムの代わりにグラフを用いた.
Aを再配置して、再配置されたAを記憶する.
複製配列Bを定義するcompare B
-compare Bで数値iを検索します.
-ベクトルAの最大値を見つけ(見つけたら要素を削除)、現在のcomapre Bと同じインデックス位置に配置します.
-compare Bの現在の要素を削除します.
-もちろん周波数-1
100 x 100 x 50(最大N)=50万はintで表すことができます.
次はコード全体です.
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
//numList는 0~ 100까지 숫자의 빈도수를 나타냄
vector<int> A;
int N, * B, numList[101] = {};
int* relocation_A, * compare_B;
void init() { //초기설정
relocation_A = new int[N];
compare_B = new int[N];
B = new int[N];
for (int i = 0, temp; i < N; i++) {
scanf("%d", &temp);
A.push_back(temp);
}
for (int i = 0, temp; i < N; i++) {
scanf("%d", &temp);
B[i] = temp; //결괏값계산용 B
compare_B[i] = temp; //비교용 B
}
for (int i = 0; i < N; i++) //빈도수카운트
numList[B[i]]++; //해당숫자의 빈도수를 + 1
}
int find_min() { //A 배열중 최솟값을 찾아 원소를 삭제후 리턴(pop)
int min = 0x7fffffff;
int min_index = 0;
for (int i = 0; i < A.size(); i++) { //A크기만큼
if (min > A[i]) {
min = A[i]; //최솟값갱신
min_index = i;
}
}
A.erase(A.begin() + min_index); //해당원소를 지움
return min;
}
void relocation() { //A배열을 재배치하는함수
//i : 현재숫자
for (int i = 100; i >= 0; i--) { //모든 빈도수를 체크
while (numList[i] > 0) { //빈도수전부..
for (int j = 0; j < N; j++) { //비교B배열 탐색
//비교B배열중 현재숫자를 찾음
if (compare_B[j] == i) {
int element = find_min(); //A배열에서 현재 최솟값을 찾음
//재배열된 A배열에 B와 같은 인덱스에 값을 넣음
relocation_A[j] = element;
numList[i]--; //현재숫자 빈도수 감소
compare_B[j] = -1; //비교 B배열 값삭제
}
}
}
}
}
void printAll() {
int s = 0;
for (int i = 0; i < N; i++)
s += relocation_A[i] * B[i];
printf("%d", s);
}
int main(void) {
scanf("%d", &N);
init();
relocation();
printAll();
return 0;
}
Reference
この問題について([白俊C+]1026宝物), 我々は、より多くの情報をここで見つけました https://velog.io/@cldhfleks2/1026テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol