程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LightOJ

LightOJ

編輯:關於C++

題目大意:迷宮裡面有n扇門,每扇門有相應的值,假設第i扇門的值為xi,如果xi > 0,那麼xi分鐘後,走該扇門就可以走出迷宮了,如果xi < 0,表示走了該扇門之後,需要abs(xi)分鐘後才能回到原點,問走出迷宮的期望是多少

解題思路:假設有k扇門(正值用x表示,負值用y表示)期望是d的話
那麼d = 1 / k * (x1 + x2 + x3 + .. xn) + 1 / k * (abs(y1) + abs((y2) + … + abs(ym) + m * d)
表示有1/k的概率選到任意一扇門,走到值為正的門需要x分鐘,走到正門後就可以直接出去了,所以期望就為1/k * x
如果是負數的話,需要走y分鐘,y分鐘後回到原點,就要加上期望了,所以期望就是1/ k * (y + d)

#include
#include
#include
using namespace std;
const int N = 110;
const double esp = 1e-5;
int num[N];
int n, cnt;
int gcd(int a, int b) {
    return a == 0 ? b :  gcd(b % a, a);
}

void solve() {
    int t = 0;
    for(int i = 0; i < n; i++)
        t = t + (num[i] > 0 ? num[i] : -num[i]);
    int g = gcd((n - cnt), t);
    printf("%d/%d\n", t  / g, (n - cnt) / g);

}

int main() {
    int test, cas = 1;
    scanf("%d", &test);
    while(test--) {
        scanf("%d", &n);
        cnt = 0;
        for(int i = 0; i < n; i++) {
            scanf("%d", &num[i]);
            if(num[i] < 0)
                cnt++;
        }
        printf("Case %d: ", cas++);
        if(cnt == n) {
            printf("inf\n");
            continue;
        }
        solve();
    }
    return 0;
}
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved