题解 | #摆火柴#

1. 首先需要字典映射。
2. 当遇到选择列表的时候，可以考虑回溯。
3. 注意先要按照题意排序，按照排序（偏贪心）的基础上，在进行回溯。
4. 最后的结果记得在字母排序

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

bool backtrack(map<int,int>& mt, vector<pair<int,int>> v, string& ret, int n  ){
    //base case
    if(n==0){
        return true;
    }

    for(int i =0; i< v.size();i++){
        if(v[i].second<=n){//当前得满足剩余的火柴棍得数目
            ret.push_back(v[i].first+'0');
            bool res = backtrack(mt,v,ret,n-v[i].second);//当前字符以及对应得剩余火柴棍数
            if(res) return true;
            ret.pop_back();//回溯
        }
    }

    return false;
}



int main(){

    map<int,int> nums;
    nums[1]=2;
    nums[2]=5;
    nums[3]=5;
    nums[4]=4;
    nums[5]=5;
    nums[6]=6;
    nums[7]=3;
    nums[8]=7;
    nums[9]=6;


    int n,m,x;
    while(cin>>n>>m){
        vector<pair<int,int>> v;
        for(int i =0; i< m;i++){
            cin>>x;
            v.push_back({x,nums[x]});//数字以及对应的火柴棍的数量
        }

        sort(v.begin(),v.end(),[](pair<int,int> a, pair<int,int> b){
            if(a.second!=b.second){
                return a.second< b.second;//火柴棍少的放在前面
            }else{
                return a.first>b.first; //数字大的放前面
            }
        });

        string res="";
        //回溯，来找在满足排序条件下最终能组成得字符串
        backtrack(nums,v,res,n);//当前字符以及对应得剩余火柴棍数
        sort(res.begin(),res.end(),[](char a, char b){
            return a>b;//确保数字从大到小排序，这样得到的就是最大得数字
        });

        cout<<res<<endl;

    }


    return 0;
}