Written by daweibayu
on July 05, 2017

Poj 1012

不知不觉毕业五年了，看了下 poj，上一次 submmit 竟然是在 13 年 10 月份，逝者如斯。

具体代码如下，以后有时间再更新思路。

#include <iostream>

// 用来记录结果，避免重复计算
int result[20] = {0};

// n 为最终的结果，k 为人数，这个函数是用来计算两个值是否匹配
bool isRight(int n, int k) {
    
    //代表每一轮剩余的数量
    int remain[20] = {0};
    
    remain[0] = 0;
    
    for (int t = 1; t <= k; t ++) {
        // 每一轮单位长度
        int unitLength = 2 * k - t + 1;
        int lengthForThisTurn = n - remain[t - 1];
        
        if (lengthForThisTurn <= k) {
            return false;
        }
        
        if (lengthForThisTurn <= unitLength) {
            remain[t] = unitLength - lengthForThisTurn;
        } else if (lengthForThisTurn > unitLength) {
            int remainder = lengthForThisTurn % unitLength;
            if (remainder == 0) {
                remain[t] = 0;
            } else if (remainder > k) {
                remain[t] = unitLength - remainder;
            } else {
                return false;
            }
        }
    }
    return true;
}

// 计算总的数量，有剪枝
int calculateJosef(int k) {
    int i = 1;
    
    while (true) {
        int n = i * (k + 1);
        if(isRight(n, k)) {
            return n;
        }
        if (isRight(n + 1, k)) {
            return n + 1;
        }
        i ++;
    }
}

int main(int argc, const char * argv[]) {
    int k;
    while (scanf("%d", &k) && k != 0) {
        if (result[k] == 0) {
            result[k] = calculateJosef(k);
        }
        printf("%d\n", result[k]);
    }
    return 0;
}

← → Top