题解 | #消灭怪物#

暴力递归回溯遍历所有可能的情况：

#include<bits/stdc++.h>
using namespace std;

struct node {
    int val,line;
};
int ans = 1000000+10;

vector<node> arr(15);
vector<bool> vis(15);
void dfs(int n,int curM,int cnt){

    if(curM <= 0){
        ans = min(ans,cnt);
        return;
    }
    for (int i = 0; i <n; ++i) {
        // arr[i]  为选取的目标
        if(vis[i]){    //选过了就跳过
            continue;
        }
        int nextM = curM;
        if(curM <= arr[i].line){        //可以暴击
            nextM -= arr[i].val*2;
        }else{
            nextM -= arr[i].val;
        }
        vis[i] = true;
        dfs(n,nextM,cnt+1);
        vis[i] = false;
    }
}

int main() {
    int t;  cin >> t;
    while(t--){
        int n,m;  cin >> n >> m;

        // 录入数组
        for(int i=0;i<n;i++){
            cin >> arr[i].val >> arr[i].line;
        }

        //初始化
        for (int i = 0; i < n; ++i) {
            vis[i] = false;
        }
        ans = 100;
        dfs(n,m,0);
        if(ans == 100){
            ans = -1;
        }
        cout << ans << endl;
    }
    return 0;
}