题目原址

http://codeforces.com/contest/1082/problem/A

题目内容

一共n页书，现在位于第x位，想要看第y页，每次只能翻d页，注意总能翻到第1页和第n页。

Vasya想知道自己能否在经过无数次翻书后看到第y页的内容。

如果可以，请给出最少需要翻几次书。

题目解析

类似一个模除的问题。

首先思考无法翻到第y页的情况，即：

①直接翻翻不到

②在到达第1页和第n页后也翻不到

对应的式子引出的是：

直接翻不到：

abs(y - x) % d ！= ；

第1页翻不到：

abs(y - ) % d !=

第n页翻不到：

abs(n - y) % d !=

因此翻不到的情况很好判断。注：以下简记左不通和右不通分别代表第一页翻不到和第n页翻不到。

再看最小翻阅次数，这里可以详尽的判断所有情况，也可以统一完成，本人采用的是详尽的判断。

将所有可能性列举出来，即左不通而右通，那么最短翻阅只有右侧的一种方式。

对应的代码部分为：

if(abs(y - ) % d != ){    //左侧不通

                //int temp = need(x, y, d);

                if(abs(n - y) % d != ){    //右侧不通

                    puts("-1");

                    continue;

                }

                else {

                    count += need(x, n, d);

                    count += need(n, y, d);

                    cout << count << endl;

                    continue;

                }

}

其中，need（）函数用来计算从x到y在每次翻阅d的情况下直接到达需要的翻阅次数，如下：

int need(int x, int y, int d){    //3 - 6 3

    if(abs(y - x) % d == ){

        return abs(y - x) / d;

    }

    else {

        return abs(y - x) / d + ;

    }

}

当右侧不通，而左侧通的时候，情况类似上述：

else if(abs(n - y) % d != ){    //右侧不通

                //int temp = need(x, y, d);

                count += need(x, , d);

                count += need(, y, d);

                cout << count << endl;

                continue;

}

而当左右都可通过的时候，只需计算左右两种方式中翻阅数的最小者即可。

else{

            int left = need(x, , d) + need(, y, d);

            int right = need(x, n, d) + need(n, y, d);

            count = min(left, right);

            cout << count << endl;

            continue;

}

题目也可以将不通返回正无穷，从而在返回最小值的过程中失效，减少判断。

题目总结

很简单的题目，没有考察到算法知识，只是考验编程者对于多种判断情况的处理。做题时应先想好思路再完成。

巴特西

A. Vasya and Book

题目原址

题目内容

题目解析

题目总结

最新文章

热门文章