[白俊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配列を整理するために,階調アルゴリズムの代わりにグラフを用いた.
  • すべての周波数をチェックするnumListを作成します.(最大要素サイズ100、生成101個)
  • 大きさが可変なベクトルAアレイ;
    Aを再配置して、再配置されたAを記憶する.
    複製配列Bを定義するcompare B
  • numList[i]は、周波数が0になるまで、100から0までナビゲートするデジタルiの周波数である.
    -compare Bで数値iを検索します.
    -ベクトルAの最大値を見つけ(見つけたら要素を削除)、現在のcomapre Bと同じインデックス位置に配置します.
    -compare Bの現在の要素を削除します.
    -もちろん周波数-1
  • 李京宇が最悪の場合A、Bのすべての要素が100であれば、
    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;
    }