crlmax
crlmax
采纳率75%
2020-06-21 12:06

这题怎么做啊?求C++代码

40
已采纳

狂暴的老师(rage)

【题目背景】

有 n 个同学(从 0 开始编号)在学习启发式的信奥课,同学们排队向老师提问。每 个同学问的问题不同,因此答疑时长不同,设第 i 个同学的答疑时长为 ti;每个同学的 耐心值也不同,设第 i 个同学的耐心为 pi。 如果一个同学等待太久,他会暴躁。每个同学的暴躁程度 gi 等于排在他前面的同 学的答疑时长之和与自身耐心的差值,即:gi = t0 + t1 +···+ ti−1 −pi。 如果同学们很暴躁,老师会狂暴。老师的狂暴程度 r 等于所有同学暴躁程度 gi 的 最大值,即:r = maxn−1 i=0 gi。 改变 n 个同学的排队顺序,老师的狂暴程度可能会发生变化。求所有的排队顺序 中,老师的狂暴程度的最小值 minr。

【输入格式】

从标准输入读入数据。 第一行为一个正整数 n(1≤n≤1,000),表示有 n 位同学。 第二行到第 n+1 行,每行两个整数,分别是 ti(0≤ti ≤1,000)和 pi(0≤ pi ≤1,000)。

【输出格式】

输出到标准输出。 输出共一行,表示老师狂暴程度 r 的最小值。

【样例 1 输入】

3

5 1

1 4

2 2

【样例 1 输出】

2

求C++代码,在线等

另外,我用人格担保,回答了正确了肯定是要采纳的

各位大佬求救救

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

1条回答

  • caozhy 回答这么多问题就耍赖把我的积分一笔勾销了 10月前
    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    int minr;
    int * p;
    int * t;
    
    int calc(int * seed, int sn)
    {
        int mr = 0;
        int pt = 0;
        for (int i = 0; i < sn; i++)
        {
            if (mr < p[seed[i]] * pt) mr = pt - p[seed[i]];
            pt += t[seed[i]];
        }
        return mr;
    }
    
    void arrange(int * seed, int sn, int n)
    {
        if (sn == n)
        {
            int mr = calc(seed, sn);
            if (mr < minr) minr = mr;
            return;
        }
        for (int i = 0; i < n; i++)
        {
            int used = 0;
            for (int j = 0; j < sn; j++)
            {
                if (seed[j] == i)
                {
                    used = 1;
                    break;
                }
            }
            if (!used && calc(seed, sn) < minr)
            {
                int * seed1 = new int[n];
                memcpy(seed1, seed, sizeof(int) * sn);
                seed1[sn] = i;
                arrange(seed1, sn + 1, n);
                delete[] seed1;
            }
        }
    }
    
    int main()
    {
        minr = 0x7fffffff;
        int n;
        cin >> n;
        p = new int[n];
        t = new int[n];
        for (int i = 0; i < n; i++)
        {
            cin >> t[i];
            cin >> p[i];
        }
        int * seed = new int[n];
        arrange(seed, 0, n);
        delete[] seed;
        delete[] p;
        delete[] t;
        cout << minr;
        return 0;
    }
    
    

    问题解决的话,请点下采纳

    点赞 1 评论 复制链接分享