Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //test data:
- // 8 80.0 1.0
- // 7 1 6 3 4 5 6 5
- // 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
- //output:
- // 0.706194
- // 5 6 5 4 3 1 6 7
- // 0.8 0.7 0.6 0.5 0.4 0.2 0.3 0.1
- #include <iostream>
- #include <algorithm>
- using namespace std;
- // will work bad for cnt > 10 because 10! = 3628800
- int perm[] = {0,1,2,3,4,5,6,7,8,9};
- int bestPerm[10];
- double sizes[10], L[10];
- double calc(int cnt, double M, double K, double T) {
- double res = 0.0, usedMemory = 0.0;
- for(int i = 0; i < cnt; i++) {
- int ind = perm[i];
- res += K * sizes[ind] / (M - L[ind] * usedMemory - (T - usedMemory));
- usedMemory += sizes[ind];
- }
- return res;
- }
- int main() {
- int cnt;
- double M,K,T = 0.0;
- cin >> cnt >> M >> K;
- for(int i = 0; i < cnt; i++)
- cin >> sizes[i], T += sizes[i];
- for(int i = 0; i < cnt; i++)
- cin >> L[i];
- double bruteRes = 1e16;
- int bruteCnt = 1;
- for(int i = 2; i <= cnt; i++)
- bruteCnt *= i;
- for(int i = 0; i < bruteCnt; i++) {
- double curRes = calc(cnt, M, K, T);
- if( bruteRes > curRes ) {
- bruteRes = curRes;
- for(int j = 0; j < cnt; j++)
- bestPerm[j] = perm[j];
- }
- next_permutation(perm, perm + cnt);
- }
- cout << bruteRes << "\n";
- for(int i = 0; i < cnt; i++)
- cout << sizes[bestPerm[i]] << " ";
- cout << "\n";
- for(int i = 0; i < cnt; i++)
- cout << L[bestPerm[i]] << " ";
- cout << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement