Oi_oier 2022-07-15 09:17 采纳率: 83.3%
浏览 35
已结题

HELP!求此题的代码!

背包问题?什么牛马?还是贪心?em求此题的代码,各位大奆帮帮忙

img

  • 写回答

2条回答 默认 最新

  • 关注

    运行结果及代码如下:
    例1:

    img

    例2:

    img

    代码:

    #include <iostream>
    using namespace std;
    
    //1判断在n天内,是否有所有考试科目
    int isContainAll(int m, int* d, int t)
    {
        for (int i = 1; i <= m; i++)
        {
            int j = 0;
            for (; j < t; j++)
            {
                if (d[j] == i)
                    break;
            }
            if (j >= t) //t天内没有i科目的考试,不满足要求
                return 0;
        }
        return 1;
    }
    
    //2在t天内,如果出现多次i科目的考试,只保留最后1次的天数
    void deald(int* d, int t, int m)
    {
        for (int i = t - 1; i >= 0; i--)
        {
            if (d[i] == 0) continue;
    
            //如果d[i]不为0,将之前的=d[i]的全部置0
            for (int j = 0; j < i; j++)
            {
                if (d[j] == d[i])
                    d[j] = 0;
            }
    
        }
    }
    
    //获取数组中从start开始不为0的元素的第一个位置
    int getpos(int* d, int t,int start)
    {
        for (int i = start; i < t; i++)
        {
            if (d[i] != 0)
                return i;
        }
        return 0;
    }
    
    
    
    //3判断在t天内,是否能够保证所有的科目都能完全准备完
    int isFull(int* d,int t, int m, int* p)
    {
        int shift = 0;
        int start = 0;
        for (int i = 0; i < m; i++)
        {
            int pos = getpos(d, t, start);
            //判断是否有足够的天数复习
            if (pos - start + shift < p[d[pos]])
                return 0;
            else
            {
                shift = pos - start + shift - p[d[pos]];
                start = pos + 1;
            }
        }
        return 1;
    }
    
    
    
    
    int main()
    {
        int n, m;
        int* d, * p;
        int sum = 0; //所有科目一共需要准备的天数
        cin >> n >> m; //输入n和m
        d = new int[n];
        p = new int[m];
        //输入di
        for (int i = 0; i < n; i++)
            cin >> d[i];
        //输入mi
        for (int i = 0; i < m; i++)
        {
            cin >> p[i];
            sum += p[i];
        }
    
    
        //需要的天数至少为sum + m ,sum天准备,m天考试
        int t = sum + m;
    
        for (; t <= n; t++)
        {
            //从t-10,判断是否包含了所有的科目
            if (isContainAll(m, d, t))
            {
                deald(d, t, m); //处理d
                if (isFull(d, t, m, p))
                {
                    cout << t;
                    return 0;
                }
            }
    
        }
    
        cout << "-1";
        return 0;
    }
    
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论 编辑记录
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 8月26日
  • 已采纳回答 8月18日
  • 创建了问题 7月15日

悬赏问题

  • ¥50 hyper默认的default switch
  • ¥15 网站打不开,提示502 Bad Gateway
  • ¥20 基于MATLAB的绝热压缩空气储能系统代码咨询
  • ¥15 R语言建立随机森林模型出现的问题
  • ¥20 unity内置语言切换的按钮设置
  • ¥15 中级微观经济学,生产可能性边界问题
  • ¥15 TCP传输时不同网卡传输用时差异过大
  • ¥15 请各位看看我写的属于什么算法,或者有更正确的写法?
  • ¥15 html5 qrcode 扫描器
  • ¥15 爬取网页信息并保存需要完整代码