Untitled

 avatar
unknown
c_cpp
2 years ago
1.5 kB
15
Indexable
// #define Many_SubTask
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(a) begin(a), end(a)
#define pb push_back
#define pii pair<int, int>
#define F first
#define S second
#define mp make_pair
const int mod = 998244353;
const int inf = 1e18;
const int MAX_FILE_NUM = 5;

int disk[MAX_FILE_NUM + 5][2];
bool choose[MAX_FILE_NUM + 5];

bool ans[MAX_FILE_NUM + 5];
int Ans_Total_SZ = 1e9;

int Deleted_File_Num;
int Target_SZ;

void find_sol(int cur_file, int choosed_file, int Total_SZ) {
    if (choosed_file == Deleted_File_Num) {  // already choose Deleted_File_Num files
        if (abs(Total_SZ - Target_SZ) < abs(Ans_Total_SZ - Target_SZ)) {  // beter than answer
            for (int i = 1; i <= MAX_FILE_NUM; i++) ans[i] = choose[i];
            Ans_Total_SZ = Total_SZ;
        }
        return;
    }
    if (cur_file > MAX_FILE_NUM) return;
    // choose
    choose[cur_file] = true;
    find_sol(cur_file + 1, choosed_file + 1, Total_SZ + disk[cur_file][1]);
    choose[cur_file] = false;
    // not choose
    find_sol(cur_file + 1, choosed_file, Total_SZ);
}

signed main() {
    for (int i = 1; i <= MAX_FILE_NUM; i++) {
        cin >> disk[i][0] >> disk[i][1];
    }
    Deleted_File_Num = 2;
    Target_SZ = 5;
    find_sol(1, 0, 0);
    for (int i = 1; i <= MAX_FILE_NUM; i++) {
        if (ans[i] == true) {
            cout << disk[i][0] << ' ';    // print file name
            disk[i][0] = disk[i][1] = 0;  // delete file
        }
    }
}
Editor is loading...