m0_61561989 2021-11-06 21:06 采纳率: 100%
浏览 27
已结题

想问个题目,用C++的函数(递归)做,并想问下是否有一般的好的算法

题目 - 通信系统
描述
某通信公司需要购置一个通信系统,这个系统由几个设备组成,每个设备都有几个不同的厂商,他们提供的设备的带宽和价格有所不同。
系统的总带宽B是几个设备中带宽的最小值,而系统的价格P则是几个设备的价格最和。
给出每个设备的所有厂商的设备带宽和价格,请你选择一种方案,使得系统的B/P尽可能大(即同样的价格买到的带宽尽可能大)
关于输入
第一行包含一个整数t(1<=t<=10),表示输入数据的组数,接下来是t组测试数据。
每组测试数据第一行是一个整数n(1<=n<=100),表示通信系统由n个不同的设备组成。
接下来n行,每行是一种设备的厂商信息。第一个整数是mi,表示第i个设备的厂商数目,接下来mi个数对,每个数对表示一个厂商提供的设备的带宽和价格。
关于输出
对每组测试数据,输出最大的B/P值,保留到小数点后3位。
例子输入
1

3

3 100 25 150 35 80 25

2 120 80 155 40

2 100 100 120 110
例子输出
0.649

  • 写回答

1条回答 默认 最新

  • Roc-xb 领域专家: 后端开发技术领域 2021-11-06 22:08
    关注

    针对所有的带宽情况,分别计算出最大的B/P值。
    带宽总数为m1+m2+...+mn,暂时不考虑重复情况,然后将每个设备的不同选择情况按价格从小到大排序,于是针对每种带宽选择每个设备满足条件的价格最小的设备,然后求出B/P,因为价格从小到大排序,所以求出的是针对该带宽的最大的B/P,最后求出所有带宽情况下的最大值。

    
    #include <stdlib.h>
    #include <iostream>
    
    using namespace std;
    
    struct SYS { int b, p; } sys[100][100];
    
    int cmp(const void * a, const void * b)
    {
     SYS * c = (SYS *) a;
     SYS * d = (SYS *) b;
     return c -> p - d -> p;
    }
    
    int main()
    {
     cout.setf(ios_base::showpoint);
     cout.setf(ios_base::fixed);
     cout.precision(3);
    
     int n;
     cin >> n;
     while(cin >> n)
     {
      int m[100], b[10000], bc = 0;
      for(int i = 0; i < n; i++)
      {
       cin >> m[i];
       for(int j = 0; j < m[i]; j++)
       {
        cin >> sys[i][j].b >> sys[i][j].p;
        b[bc++] = sys[i][j].b;
       }
       qsort(sys[i], m[i], sizeof(SYS), cmp);
      }
    
      double max = 0;
      for(int k = 0; k < bc; k++)
      {
       int sum = 0;
       bool could = true;
       for(int i = 0; i < n; i++)
       {
        int j;
        for(j = 0; j < m[i]; j++)
         if(sys[i][j].b >= b[k])
         {
          sum += sys[i][j].p;
          break;
         }
         if(j == m[i])
         {
          could = false;
          break;
         }
       }
       if(could)
       {
        double temp = double(b[k]) / sum;
        max = max > temp ? max : temp;
       }
        //max >?= double(b[k]) / sum;
      }
    
      cout << max << endl;
     }
    
    
     return 0;
    }
    
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

问题事件

  • 系统已结题 11月14日
  • 已采纳回答 11月6日
  • 修改了问题 11月6日
  • 创建了问题 11月6日