小C的英语——初级模拟

桃扇骨 2022-06-16 14:08 82阅读 0赞

Tink:  
1建立抽象模型，进行推演  
2通过分类讨论可发现问题奇数总页数可通过转化为偶数总页数，奇数查询页数同样可以通过转化为偶数查询页数，进而判断问题的最优解

小C的英语  
Time Limit: 1000MS Memory Limit: 65536KB  
Submit Statistic

Problem Description  
小C的英语很差，天天被小Y嘲笑，所以他下定决心，好好学英语，但是小C的基础很差，就去向小H去请教，小H说英语主要靠自学，就给了小C一本神奇的字典，这本字典有 n 页，每当小C有不会的单词，这本字典会自动告诉你这个单词在第几页，小C只要去翻到这一页就可以了，但是小C有强迫症，他只想一页一页的翻，所以他只从字典的第一页开始翻或者是字典的最后一页开始翻。  
这本字典翻开时显示左右两页，偶数页在左边，奇数页在右边。那么小C至少翻几次才可以找到他想要的单词？

Input  
输入数据有多组（数据组数不超过 1000），到 EOF 结束。  
每一行有两个数字 n, p (1 <= p <= n <= 10000)，分别代表这本字典有 n 页，小C要找的单词在第 p 页。

Output  
输出一个数字 k，代表小C至少翻几次才可以找到他想找的单词。

Example Input  
6 2  
5 4

Example Output  
1  
0

Hint  
对于第一组数据，字典共 6 页，如果从第 1 页开始翻（开始时字典打开在第 1 页），翻第一次，到第 2、3 页，找到了要找的单词；如果从最后一页（第 6 页）开始翻（开始时字典打开在第 6 页），翻第一次，到 4、5 页，再翻第二次，到 2、3 页，找到了要找的单词。  
因此从第一页开始翻的次数小于从最后一页开始翻的次数，输出 1。

Author  
「山东理工大学第一届ACM知识挑战赛（机试）」C~K

以下为Accepted代码

#include <bits/stdc++.h>
    
    using namespace std;
    
    int main()
    {
        int n, p, a, b;
        while(scanf("%d %d", &n, &p) != EOF){
            if(n%2 == 0){
                if(p%2 == 0){
                    a = p/2;
                    b = (n-p)/2;
                }
                else if(p%2 != 0){
                    a = (p-1)/2;
                    b = (n-(p-1))/2;
                }
            }
            else if(n%2 != 0){
                if(p%2 == 0){
                    a = p/2;
                    b = (n-1-p)/2;
                }
                else if(p%2 != 0){
                    a = (p-1)/2;
                    b = (n-1-(p-1))/2;
                }
            }
            printf("%d\n", min(a, b));
        }
        return 0;
    }
    
    
    /***************************************************
    User name: 
    Result: Accepted
    Take time: 0ms
    Take Memory: 196KB
    Submit time: 2017-05-16 21:51:31
    ****************************************************/