题目大意不陈述了， 最后主要求选出的N组数据，min(B）/sum（P）的最大值。
主要的难点是两个变量，求最大值，按照数学的思想，除非这两个有某种联系，然后利用单调性求解，否则只有一条出路，定其中一个变量。 当min(B) 或者sum(P) 确定后，剩下的工作就是就最小值。显然这里定min(B)较为合理，毕竟sum(P)还需要求和。应该是使用的dfs或者贪心，对专有名词不太懂，具体请看代码。
#include<iostream> #include<string> #include <iomanip> #include <fstream> using namespace std; struct BPData { int bandWidth; int price; }; int test_size; int product_size; int product_case[100] = {}; BPData detail[100][100] = {}; int max_search_bandwidth = 65535; //求B/P值 double getBP(int minBandWidth) { //下次使用的minBandwidth，由于要更新minBandwidth，所以感觉排序没太大必要 int nextBandWidth = 0; int sum_price = 0; for (int i = 0; i < product_size; i++) { int temp_price = 65535; for (int j = 0; j < product_case[i]; j++) { if (detail[i][j].bandWidth >= minBandWidth) { if (temp_price > detail[i][j].price) { temp_price = detail[i][j].price; } } else if (nextBandWidth < detail[i][j].bandWidth) // 寻找下一个banwidth { nextBandWidth = detail[i][j].bandWidth; } } sum_price += temp_price; } //计算当前值 double temp_result = ((double)minBandWidth) / sum_price; if (nextBandWidth) { double next_result = getBP(nextBandWidth); return next_result > temp_result ? next_result : temp_result; } return temp_result; } int main() { // ifstream in("d:\\document\\test.txt"); cin >> test_size; int sum_test = 0; while (sum_test < test_size) { max_search_bandwidth = 65535; sum_test++; cin >> product_size; for (int i = 0; i < product_size; i++) { cin >> product_case[i]; int line_max = 0; for (int j = 0; j < product_case[i]; j++) { cin >> detail[i][j].bandWidth >> detail[i][j].price; if (line_max < detail[i][j].bandWidth) { line_max = detail[i][j].bandWidth; } } if (max_search_bandwidth > line_max) { max_search_bandwidth = line_max; } } double bp = getBP(max_search_bandwidth); cout.setf(ios::fixed); cout << fixed << setprecision(3) << bp << endl; } system("pause"); return 0; }