摆火柴_百度笔试题

牛客766902794号

贪心+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)

CharmsGraker

#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)

陆小凤S

参考评论区的@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)

hideinsea

对于一个数字，当然是：

位数越多，数值越大
起始位数字越大，数值越大

那么，对于可用的数字，如果消耗相同的火柴数，那么我们保留数值最大的即可；

此外，我们为了获得最多的位数，肯定优先选择消耗火柴数最少的数字。

#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)

laoyan

首先将每次的允许使用的火柴数字和这个数字需要花费的火柴树用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)

OFFER/OFFER

#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)

牛客902869023号

#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)

Tesla3

#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)

牛客843191783号

个人思路解析：

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)

摆火柴

输入描述:

输出描述:

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题