HDU 5742

题意：
    给出序列 a[] 的其中几项，已知序列满足非减，并且 0 <= ai <= 100，问 (a1 + a2) / ( ∑ai)最大可能是多少

分析：
    保证 a1,a2尽可能大，其余尽可能小即可

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 int t, n, m;
 5 int a[105];
 6 int GCD(int a, int b)
 7 {
 8     return b == 0? a : GCD(b, a % b);
 9 }
10 int main()
11 {
12     scanf("%d", &t);
13     while (t--)
14     {
15         memset(a, -1, sizeof(a));
16         scanf("%d%d", &n, &m);
17         if (m == 0 || n == 2)
18         {
19             puts("1/1"); continue;
20         } 
21         for (int i = 1; i <= m; i++)
22         {
23             int x, y;
24             scanf("%d%d", &x, &y);
25             a[x] = y;
26         }
27         int Min=0;
28         for (int i = n; i > 2; i--)
29         {
30             if (a[i] == -1) a[i] = Min;
31             else Min = a[i];
32         }
33         if (a[1] == -1) a[1] = 100;
34         if (a[2] == -1) a[2] = a[1];
35         int tu = a[1] + a[2], td = 0;
36         for (int i = 1; i <= n; i++) td += a[i]; 
37         int gcd = GCD(tu, td);
38         tu /= gcd;
39         td /= gcd;
40         printf("%d/%d
", tu, td);
41     }
42 }

我自倾杯，君且随意