首页 > 试题广场 >

摆火柴

[编程题]摆火柴
  • 热度指数:665 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
牛牛给了小度n根火柴和m种数字(m只能是1到9),小度只能摆这m种数字,小度想知道能摆出来最大的数的多少。

如图所示: 摆数字1,2,3,4,5,6,7,8,9 分别需要花费 2,5,5,4,5,6,3,7,6根火柴。

输入描述:
第一行两个数n,m。 
第二行m个数,表示小度可以摆放的数。


输出描述:
一行表示答案。
示例1

输入

20 4
3 7 8 4

输出

777773

说明

火柴得使用完
贪心+dp

#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;

int main()
{
    string res = "";
    
    int num[10] = {0,2,5,5,4,5,6,3,7,6};
    int n,m;
    cin>>n>>m;
    int da[m+10];
    for(int i=0;i<m;i++) cin>>da[i];
    
    int f = 100;
    int id = -1;
    for(int i=0;i<m;i++) {
        if(num[da[i]] < f) f = num[da[i]];
    }
    for(int i=0;i<m;i++) if(f == num[da[i]]) id = max(id,da[i]);
    
    
    while(n >=30)
    {
        res += to_string(id);
        n-=num[id];
    }
    //cout<<n<<endl;
    
    long long dp[n+1];
    for(int i=0;i<=n;i++) dp[i] = -1;
    for(int i=0;i<m;i++)
    {
        if(num[da[i]] <= n && dp[num[da[i]]] < da[i]) dp[num[da[i]] ] = da[i];
        //cout<<da[i]<<" "<<num[da[i]]<<" "<<dp[num[da[i]]]<<endl;
    }
    dp[0] = 0;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(i - num[da[j]] >= 0 && dp[i - num[da[j]]] >0)
            {
                long long newval = dp[i - num[da[j]] ] *10 + da[j];
                dp[i] = max(dp[i],newval);
            }
        }
    }
   // cout<<dp[n]<<endl;
       if(res.length() == 0) 
       {
           cout<<to_string(dp[n])<<endl;
           return 0;    
    }
       string newstr =  to_string(dp[n]);
    for(int i=0;i<newstr.length();i++)
    {
        if(res[0] >= newstr[i]) 
        {
            res =  newstr.substr(0,i) + res + newstr.substr(i,newstr.length() - i); 
            break;
        }
    }
    cout<<res<<endl;
    
    return 0;
}

发表于 2022-03-22 17:57:13 回复(0)
#include<bits/stdc++.h>

int dig_weight[] = {2, 5, 5, 4, 5, 6, 3, 7, 6};

using namespace std;

int main() {
    int capacity, n_item;
    cin >> capacity >> n_item;
    vector<int> weight(9, 0x3ffffff);
    for (int i = 0; i < n_item; ++i) {
        int dig;
        cin >> dig;
        weight[dig - 1] = dig_weight[dig - 1];
    }
    vector<int> dp(capacity + 1,-0x3ffffff);
    dp[0] = 0;
    for (int i = 1; i <= 9; ++i) {
        for (int j = weight[i - 1]; j <= capacity; ++j) {
            dp[j] = max(dp[j], dp[j - weight[i - 1]] + 1);
        }
    }
    string ans;
    for (int i = 9, j = capacity; i >= 1; --i) {
        for (int cost = weight[i - 1]; j >= cost && dp[j] == dp[j - cost] + 1; j -= cost) {
            ans += (i + '0');
        }
    }
    cout << ans;
}

发表于 2022-03-20 19:32:35 回复(2)
参考评论区的@CharmsGraker的代码写的java版本,略微修改了下实现方式,总体思路就是找到一个最长的字符串并且让大的数在前面。 借助一个长度为火柴数量+1的数组dp,除0处的元素外都置为很小的负数(这样就能保证倒序遍历的时候能够遍历到0,而不会遍历到其他的位置),然后遍历给定的数字时所需的火柴数量,并在dp的每一个位置处记录该位置能够有的数字的最大长度,最终在最后的位置处就一定是该数字能够拥有的最大长度。然后倒序遍历,找出大的数在前面的该最大长度的数字。
import java.util.*;
import java.io.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static int[] cnt = new int[]{2,5,5,4,5,6,3,7,6};
    private static int maxNum = 0;
    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] s = in.readLine().split(" ");
        int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
        s = in.readLine().split(" ");
        Integer[] can = new Integer[m];
        for(int i = 0; i < m; i++){
            can[i] = Integer.parseInt(s[i]);
        }
        Arrays.sort(can);
        int[] dp = new int[n+1];
        Arrays.fill(dp, -0x3ffffff);
        dp[0] = 0;
        for(int i = 0; i < m; i++){
            for(int j = cnt[can[i]-1]; j <= n; j++){
                dp[j] = Math.max(dp[j], dp[j-cnt[can[i]-1]]+1);
            }
        }
        StringBuffer sb = new StringBuffer();
        for(int i = m - 1, j = n; i >= 0; i--){
            for(int cost = cnt[can[i]-1]; j >= cost && (dp[j] == dp[j-cost]+1); j -= cost){
                sb.append(can[i]);
            }
        }
        System.out.println(sb);
    }
}


发表于 2023-03-28 10:27:41 回复(0)
对于一个数字,当然是:
  • 位数越多,数值越大
  • 起始位数字越大,数值越大
那么,对于可用的数字,如果消耗相同的火柴数,那么我们保留数值最大的即可;
此外,我们为了获得最多的位数,肯定优先选择消耗火柴数最少的数字。
#include <cstdio>
#include <iostream>
#include <map>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

// 每个数字需要消耗的火柴数
constexpr int stick_cnt[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

// 对剩余的火柴可能摆放的数字情况
vector<string> possible_stuff;
// 输入中 可用的数字,以及对应的火柴消耗
vector<int> number, cnt;

// 递归判断剩余火柴可能的摆放情况
void find_fit_stuff(int rest, const string& s) {
    if (rest < 0) return;
    if (rest == 0) {
        possible_stuff.emplace_back(s);
    }
    for (int i = 0; i < cnt.size(); i++) {
        // try every number
        find_fit_stuff(rest - cnt[i], s + to_string(number[i]));
    }
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    map<int, int> mp;

    for (int i = 0; i < m; i++) {
        int x;
        scanf("%d", &x);
        // 如果当前这种火柴数消耗还没有出现过,直接加入;
        // 否则挑选数值更大的记录
        if (mp.find(stick_cnt[x]) == mp.end()) {
            mp.emplace(stick_cnt[x], x);
        } else {
            if (x > mp[stick_cnt[x]]) {
                mp[stick_cnt[x]] = x;
            }
        }
    }

    for (auto it: mp) {
        cnt.emplace_back(it.first);
        number.emplace_back(it.second);
    }

    // 假设先用消耗最少的摆放
    int min_number_cnt = n / cnt[0], rest = n % cnt[0];

    // 如果根本没有剩余,那么直接输出就可以了
    if (!rest) {
        cout << string(min_number_cnt, number[0] + '0') << endl;
        return 0;
    }

    // 持续减少最小火柴消耗的数字数量,
    // 直到能够找到一种数字排列使得所有火柴都能用完
    for (int i = 1; i < min_number_cnt && possible_stuff.size() == 0; i++) {
        find_fit_stuff(rest + i * cnt[0], "");
        min_number_cnt--;
    }

    // 优先挑选最长的,然后再考虑字典序
    sort(possible_stuff.begin(), possible_stuff.end(), [](const string& self, const string& other) -> bool {
        return self.size() == other.size() ? self > other : self.size() > other.size();
    });

    // 这里已经知道最终使用哪两个字符串进行拼凑,选一个起始位最大的作为开头
    string final_prefix(min_number_cnt, number[0] + '0');
    cout << ((final_prefix[0] > possible_stuff[0][0]) ? final_prefix + possible_stuff[0] : possible_stuff[0] + final_prefix) << endl;

    return 0;
}


发表于 2023-03-26 16:35:35 回复(0)
首先将每次的允许使用的火柴数字和这个数字需要花费的火柴树用hashmap存储起来(python里面就直接用list做了)。然后根据贪心的原理,肯定是要从花费最小的数字找起来,位数可能会越高,这样其最后组成的数字也就会越大。所以使用lambda表达式对数据字典里面的values值进行排序。接下来,拿这道题的示例举例子,如果输入是20,那么首先根据贪心算***选择数字7,那么剩下的组成就是输入13会怎么组成最大。这样就自然而然的想到使用动态规划进行解题。不过题目并没有对输入的数进行限制,因此就采用二重循环解题时间复杂度也过得去。然后需要注意的一点还是选择最大的数,假如最后算出来位数相同还需要进行大小的比较。
import sys
l = {1: 2, 2: 5, 3: 5, 4: 4, 5: 5, 6: 6, 7: 3, 8: 7, 9: 6}
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
x = {}
for i in range(a[1]):
    c.append(l[b[i]])
    x[b[i]] = l[b[i]]
x = sorted(x.items(), key=lambda x: x[1])
d = [0 * i for i in range(a[0]+1)]
s = ["" for i in range(a[0]+1)]
for j in range(a[0]+1):
    for i in range(len(x)):
        if j >= x[i][1]:
            d[j] = max(d[j], 1 + d[j - x[i][1]])
            if  (s[j - x[i][1]] != ''&nbs***bsp; j - x[i][1] == 0):        
                if s[j - x[i][1]] == '':
                    if len(s[j]) < len(str(x[i][0])):
                        s[j] = str(x[i][0])
                    elif  len(s[j]) == len(str(x[i][0])):
                        if int(s[j]) < int(str(x[i][0])):
                            s[j] = str(x[i][0])
                else:
                    if len(s[j]) < len(str(x[i][0])  + s[j - x[i][1]]):
                        s[j] = str(x[i][0])  + s[j - x[i][1]]  
                    elif len(s[j]) == len(str(x[i][0])  + s[j - x[i][1]]):
                        if int(s[j]) < int(str(x[i][0])  + s[j - x[i][1]]):
                            s[j] = str(x[i][0])  + s[j - x[i][1]]  
print(s[-1])


发表于 2023-03-10 21:37:06 回复(0)
#include <bits/stdc++.h>
using namespace std;
static int weight[10] = {0,2,5,5,4,5,6,3,7,6};
string max_str(const string& str1, const string& str2)
{
    int n1 = str1.size();
    int n2 = str2.size();
    if(n1 > n2) return str1;
    else if(n1 < n2) return str2;
    if(str1.compare(str2) < 0) return str2;
    return str1;
}
unordered_map<int,string> dp;
int main()
{
    int capacity, m;
    cin >> capacity >> m;
    vector<int> nums(m , 0);
    for(int i = 0;i < m;i++)
        cin >> nums[i];
    for(int i = 1;i <= capacity;i++)
        dp[i] = "";
    for(int j = 1;j <= capacity;j++)
        for(int i = 0;i < m;i++)
            if(j-weight[nums[i]] >= 0)
                // j == weight[nums[i]] 进行初始化
                if(dp[j-weight[nums[i]]] != "" || j == weight[nums[i]])
                    dp[j] = max_str(dp[j], to_string(nums[i]) + dp[j - weight[nums[i]]]);
    cout << dp[capacity] << endl;
    return 0;
}


发表于 2022-03-20 23:01:34 回复(0)
思路:动态规划
#include <iostream>
#include <vector>
using namespace std;
 
const vector<int> fate = { 0, 2, 5, 5, 4, 5, 6, 3, 7, 6 };
 
int comp(string s1, string s2)
{
    if (s1.size() > s2.size())
    {
        return 1;
    }
    else if (s1.size() < s2.size())
    {
        return -1;
    }
    else
    {
        return s1.compare(s2);;
    }
     
}
 
int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> set(m);
    for (int i = 0; i < m; ++i)
        cin >> set[i];
 
    vector<string> dp(n + 1, "");
    for (int i = 2; i < n + 1; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (i >= fate[set[j]])
            {
                if (dp[i - fate[set[j]]] != "" || i == fate[set[j]])
                {
                    string ns = dp[i - fate[set[j]]] + (char)(set[j] + '0');
                    int ret = comp(dp[i], ns);
                    if (ret < 0) dp[i] = ns;
                }
            }
 
        }
    }
    cout << dp[n] << endl;
 
    return 0;
}


发表于 2022-03-20 18:39:14 回复(2)
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
int n, m;
int map[10] = {0,2,5,5,4,5,6,3,7,6};
bool cmp(int a, int b){
    if(map[a] == map[b])
        return a > b;
    return map[a] < map[b];
}
bool findAns(int a[], vector<int> &vec, const int& n){
    if(n < 0)
        return 0;
    if(n == 0)
        return 1;
    for(int i = 0; i < m; i++){
        if(i != 0 && map[a[i-1]] == map[a[i]])
            continue;
        vec.push_back(a[i]);
        if(findAns(a, vec, n-map[a[i]])){
            return 1;
        }
        vec.pop_back();
    }
    return 0;
}
int main()
{
    
    
    cin >> n >> m;
    int a[11];
    for(int i = 0; i < m; i++){
        cin >> a[i];
    }
        
    sort(a, a+m, cmp);

    vector<int> vec;
    vec.clear();
    findAns(a,vec, n);
    
    sort(vec.begin(),vec.end(),[](int a, int b)->bool{return a > b;});
    for(auto i : vec)
        cout << i;
    return 0;
}
发表于 2022-02-28 21:16:34 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <unordered_map>

using namespace std;

static unordered_map<int, int> costs = {
    {1, 2}, {2, 5}, {3, 5}, {4, 4},
    {5, 5}, {6, 6}, {7, 3}, {8, 7}, {9, 6},
};

void FindNumber(const vector<int>& A, int n, int i,
                string& s, vector<string>& res) {
    // return when we find the first match
    if (!res.empty() || n == 0) {
        if (n == 0)
            res.push_back(s);
        return;
    }
    for (int j = i; j < A.size(); ++j) {
        int c = costs[A[j]];
        if (c <= n) {
            char d = (char)(A[j] + '0');
            s.push_back(d);
            FindNumber(A, n - c, j, s, res);
            s.pop_back();
        }
    }
}

void PrintMaxNumber(int n, vector<int>& A) {
    // sort A by cost in the ascending order
    // (large number first if cost equals)
    sort(A.begin(), A.end(), [](int l, int r) {
       return costs[l] != costs[r] ? costs[l] < costs[r] : r < l;
    });
    string cur;
    vector<string> res;
    FindNumber(A, n, 0, cur, res);
    if (!res.empty()) {
        // rearrange the order of characters such that the large digit
        // comes first
        sort(res[0].begin(), res[0].end(), greater<int>());
        cout << res[0] << endl;
    }
}

int main() {
    int m, n;
    cin >> n >> m;
    vector<int> A(m);
    for (int i = 0; i < m; ++i) {
        cin >> A[i];
    }
    PrintMaxNumber(n, A);
}

发表于 2022-01-09 10:43:59 回复(1)
个人思路解析:
1、用map存对应关系<火柴数,对应数字>,如果存在同样火柴数,但是更大数字的就修改map,map的key值有序
2、用数组存火柴数和数字(map不支持随机访问,map有序,所以转存数组根据火柴数大小升序)
3、已知,用最少的火柴数能摆放更多个数字,自然更大,因此计算出如果全是最小火柴数数字(个数cnt)后,剩余的火柴数d,然后减少个数,增加d值,看是否能支持摆出数字组合,如果可以,结果就是cnt个最小火柴数对应数字以及后面的数字组合合起来组成的数字。
4、对数字按照大小进行排序,就能得到最大的数字。
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
using namespace std;
set<string> ret;
vector<int> nn, ch;
void f(int num, string s) {
    if (num < 0) { return; }
    if (num == 0) { ret.insert(s); return; }
    for (int i = 0; i <nn.size(); i++) {
        f(num - nn[i], s + to_string(ch[i]));
    }
}
bool cmp(string a, string b) {
    if (a.size() == b.size()) { return a < b; }
    else return a.size() < b.size();
}
bool chcmp(char a, char b) {
    return a > b;
}
int main() {
    int n, m, a;
    cin >> n >> m;
    int num[10] = { 0,2,5,5,4,5,6,3,7,6 };
    vector<int> ve;
    map<int, int> ma;
    for (int i = 0; i < m; i++) {
        cin >> a;
        if (ma.find(num[a]) == ma.end()) { ma[num[a]] = a; }
        else {
            if (a > ma[num[a]]) { ma[num[a]] = a; }
        }
    }
    for (auto it : ma) {
        nn.push_back(it.first);
        ch.push_back(it.second);
    }
    ma.clear();
    int d = n % nn[0], cnt = n / nn[0];
    while (ret.size() == 0) {
        string s;
        d = d + nn[0]; cnt--;
        f(d, s);//找出d根火柴在限定可能性的情况下是否能刚好摆出数字。
    }
    vector<string> ss(ret.size());
    int i = 0;
    for (auto it : ret) { ss[i++] = it; }
    sort(ss.begin(), ss.end(), cmp);
    string s = ss[ret.size() - 1];//找出ss中长度最长、数字最大的组合。
    while (cnt--) { s = s + to_string(ch[0]); }
    sort(s.begin(), s.end(),chcmp);//对数字进行排序
    cout << s << endl;
    return 0;
}




发表于 2021-09-22 17:05:51 回复(0)