crlmax
2020-06-21 12:06
采纳率: 75%
浏览 170
已采纳

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

狂暴的老师（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条回答 默认 最新

  • threenewbee 2020-06-21 13:59
    已采纳 
    #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;
}

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

    已采纳该答案
    评论
    解决 无用
    打赏 举报

报告相同问题？

提交

相关推荐 更多相似问题