牛客多校(2020第6回)C Combination of Physics and Maths(欲張り)
5736 ワード
タイトルリンク:転送ゲート
問題:
この問題は1つの行列の最後の1行の数が底面積を代表して、すべての数の和は重量で、圧力の強さPを求めます a/b <= (a+c)/(b+d) <= c/d
したがって、は、選択サブマトリクスに複数の列がある場合には、2つの行数がより小さなサブマトリクス にならないように分割する.(すなわち縦に切る)、そのうちの1つは最悪ではないに違いない だから答えは単列の最大値 を探すことだ.
問題:
この問題は1つの行列の最後の1行の数が底面積を代表して、すべての数の和は重量で、圧力の強さPを求めます
したがって、
1 /*
2 a/b <= (a+c)/(b+d) <= c/d
3 ，
4 （ ），
5
6 */
7 #include
8 #include
9
10 using namespace std;
11
12 const int MAX_N = 505;
13 int matrix[MAX_N]; //
14 double max_res;
15 int n, m;
16
17 int main() {
18 ios::sync_with_stdio(false); cin.tie(0);
19 int t;
20 cin >> t;
21 while (t--) {
22 memset(matrix, 0, sizeof(matrix));
23 max_res = 0;
24 cin >> n >> m;
25
26 for (int i = 1; i <= n; i++)
27 for (int j = 1; j <= m; j++) {
28 int a;
29 cin >> a;
30 matrix[j] += a;
31 max_res = max(max_res, 1.0*matrix[j] / a);
32 }
33
34 printf ("%.8lf
", max_res);
35 }
36 return 0;
37 }
38
39 /*
40 in
41
42 1
43 3 3
44 1 3 5
45 6 8 9
46 2 7 4
47
48 out
49 4.50000000
50 */