lightoj 1027 A Dangerous Maze 期望

设答案为r,cnt为x[i] >=0的个数

那么r = 1/n *  (Σx[i](x[i] >= 0) + ∑(r - x[i])(x[i] < 0))

然后把r移项到一起解方程, 得到r = ∑|x[i]| / cnt,同除gcd。记得特判下x[i]均为负数的情况即可。

 1 #include <cstdio>
 2 #include <algorithm>
 3 using namespace std;
 4 int T,cas,n,tot,gcd,cnt;
 5 int x[110];
 6 int main()
 7 {
 8     for (scanf("%d",&T);T != 0;T--)
 9     {
10         cas++;
11         tot = cnt = 0;
12         scanf("%d",&n);
13         for (int i = 1;i <= n;i++)
14         {
15             scanf("%d",&x[i]);
16             if (x[i] >= 0)
17             {
18                 cnt++;
19                 tot += x[i];
20             }else
21                 tot -= x[i];
22         }
23         if (cnt == 0)
24         {
25             printf("Case %d: inf\n",cas); 
26             continue;
27         }
28         gcd = __gcd(tot,cnt);
29         printf("Case %d: %d/%d\n",cas,tot / gcd,cnt / gcd);
30         
31     }
32     return 0;
33 }

 

上一篇:1960: 找出矩阵中的素数


下一篇:P1049 [NOIP2001 普及组] 装箱问题 题解