编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#699 #999. 蛋蛋 Accepted 100 28 ms 380 K C++ 17 / 1.4 K s230034010 2023-10-15 15:07:27
显示原始代码
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m, ans;
vector<int> needs;
vector<vector<int>> foods;
vector<int> selected_foods;

void backtrack(int curr, vector<int> &selected, vector<int> remains) {
    if (selected.size() > ans) {
        return;
    }
    if (all_of(remains.begin(), remains.end(), [](int remain) { return remain <= 0; })) {
        if (selected.size() < ans) {
            ans = selected.size();
            selected_foods = selected;
        }
        return;
    }
    if (curr == m) {
        return;
    }

    vector<int> new_remains(n);
    for (int i = 0; i < n; ++i) {
        new_remains[i] = remains[i] - foods[curr][i];
    }
    selected.push_back(curr);
    backtrack(curr + 1, selected, new_remains);
    selected.pop_back();

    backtrack(curr + 1, selected, remains);
}

int main() {
    cin >> n;
    needs.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> needs[i];
    }

    cin >> m;
    foods.resize(m, vector<int>(n));
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> foods[i][j];
        }
    }

    ans = m + 1;
    vector<int> selected;
    backtrack(0, selected, needs);

    cout << ans;
    for (int idx : selected_foods) {
        cout << " " << idx + 1;
    }
    cout << endl;

    return 0;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:4 ms
内存:264 KiB

输入文件(1.in

1
50
1
50

答案文件(1.out

1 1

用户输出

1 1

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:4 ms
内存:380 KiB

输入文件(2.in

3
100 200 300
3
99 199 299
2 2 2
1000 1000 1000

答案文件(2.out

1 3

用户输出

1 3

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:4 ms
内存:360 KiB

输入文件(3.in

4
1 1 1 1
4
1 1 0 0
1 0 1 0
0 1 0 1
0 0 0 1

答案文件(3.out

2 2 3

用户输出

2 2 3

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:7 ms
内存:272 KiB

输入文件(4.in

5
10 20 30 40 50
5
10 10 10 10 10
0 10 10 10 10
0 0 10 10 10
0 0 0 10 10
0 0 0 0 10

答案文件(4.out

5 1 2 3 4 5

用户输出

5 1 2 3 4 5

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:5 ms
内存:264 KiB

输入文件(5.in

8
10 10 10 10 10 10 10 10
7
1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4
1
<62 bytes omitted>

答案文件(5.out

2 6 7

用户输出

2 6 7

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:4 ms
内存:352 KiB

输入文件(6.in

4
100 200 300 400
3
50 50 50 50
200 300 200 300
900 150 389 399

答案文件(6.out

2 1 3

用户输出

2 1 3

系统信息

Exited with return code 0