【OJ题目】选择客栈 | 公司新表

- 日理万妓 2024-03-26 17:18 41阅读 0赞

## 一、选择客栈 ##

### 1. 题目描述 ###

丽江河边有n家很有特色的客栈，客栈按照其位置顺序从1到n编号。每家客栈都按照某一种色调进行装饰（总共k种，用整数 0~k-1表示），且每家客栈都设有一家咖啡店，每家咖啡店均有各自的最低消费。

两位游客一起去丽江旅游，他们喜欢相同的色调，又想尝试两个不同的客栈，因此决定分别住在色调相同的两家客栈中。晚上，他们打算选择一家咖啡店喝咖啡，要求咖啡店位于两人住的两家客栈之间（包括他们住的客栈），且咖啡店的最低消费不超过p。

他们想知道总共有多少种选择住宿的方案，保证晚上可以找到一家最低消费不超过p元的咖啡店小聚。

### 2. 输入描述: ###

第一行三个整数 n，k，p，每两个整数之间用一个空格隔开，分别表示客栈的个数，色调的数目和能接受的最低消费的最高值；

接下来的n行，第i+1行两个整数，之间用一个空格隔开，分别表示i号客栈的装饰色调和i号客栈的咖啡店的最低消费。

### 3. 输出描述: ###

输出只有一行，一个整数，表示可选的住宿方案的总数。

### 4. 测试用例： ###

> 5 2 3  
> 0 5  
> 1 3  
> 0 2  
> 1 4  
> 1 5

### 5. 输出结果： ###

> 3

### 6. 解释： ###

> 2人要住同样色调的客栈，所有可选的住宿方案包括：住客栈①③，②④，②⑤，④⑤，但是若选择住4、5号客栈的话，4、5号客栈之间的咖啡店的最低消费是4，而两人能承受的最低消费是3元，所以不满足要求。因此只有前3种方案可选。

### 7.代码实现 ###

模拟过程并不好描述，博主也看了一些题解，都没有很好地讲清楚，所以将代码逐行注释，读者可以根据注释、代码进行理解，在此不再解释。

int solution(int n, int k, int p, std::vector<std::vector<std::string>>& vec) {
        
        int result;
        // TODO:
        result = 0;
        vector<int> cur(k, 0);
        vector<int> sum(k, 0);
        for (int i = 0; i < n; i++) {
        
            int color = atoi(vec[i][0].c_str()); // 第i个客栈的颜色
            int price = atoi(vec[i][1].c_str()); // 第i个客栈的价格
            cur[color]++;                      // 当前段的颜色 ++
            if (price <= p) {
                          // 证明找到了一个新的中间咖啡店
                for (int j = 0; j < k; j++) {
          // 遍历所有颜色
                    sum[j] += cur[j];          // 之前的所有颜色可以累加到总数里了
                    cur[j] = 0;                // 当前颜色清零
                }
                result -= 1;        // 注意：因为2个人不能同时住在一个咖啡店，所以咖啡店不能包括当前这个，要-1
            }
            result += sum[color];   // 最终结果，每遍历一个客栈，相当于第二个人多了一种可能性，第一个人可以用之前的所有
        }
        return result;
    }
    
    int main() {
        
    
        int n;
        int k;
        int p;
        std::vector<std::vector<std::string>> vec;
    
        std::cin >> n;
        std::cin >> k;
        std::cin >> p;
    
        std::string line, token;
        for (size_t i = 0; i < n; i++) {
        
            std::vector<std::string> s;
    
            getline(std::cin >> std::ws, line);
            std::stringstream tokens(line);
            while (std::getline(tokens, token, ' ')) {
        
                s.push_back((token));
            }
    
            vec.push_back(s);
        }
    
    
        int result = solution(n, k, p, vec);
    
        std::cout << result << std::endl;
    
        return 0;
    }

## 二、公司新表 ##

### 1.题目描述 ###

公司里为了凸显公司的特性。安装了一个n进制表。

已知新的表的时间是H:M。

时间合法的定义为H<=23 && M<=59。

时间有多少种进制定义的方式，依次打印出来。

如果有无数种解输出-1，不存在输出0。

### 2. 输入描述： ###

输入一行字符串a:b形式。

### 3. 输出描述： ###

输出答案。

### 4. 输入样例： ###

> 11:20

### 5. 输出样例： ###

> 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

### 6. 代码实现 ###

最小的进制为2，最大的进制应该为59，因为分钟数不能超过60。据此进行枚举，如果最终列表为空，则返回0；如果60进制可用，则返回1。

bool match(std::string str, int base) {
        
        int time[2] = {
         0, 0 }, t = 0;              // 定义小时和分钟数组 及 索引
        for (int i = 0; i < str.length(); i++) {
            // 遍历字符串
            if (str[i] == ':') {
                            // 如果遇到 : 证明该切换到下一组了
                t = 1;
                continue;
            }
            int x = (str[i] >= '0' && str[i] <= '9') ? (str[i] - '0') : (str[i] - 'A' + 10); // 将 char 类型转为 int
            if (x < base)                    // 如果当前值没超过进制范围，进行累加求和
                time[t] = time[t] * base + x; 
            else                             // 如果当前值已经超过了进制的范围，直接返回 false
                return false;
        }
        return time[0] < 24 && time[1] < 60; // 判断两个数字（小时和分钟）是否满足范围
    }
    
    std::vector<int> solution(std::string m) {
        
        std::vector<int> result;
        // TODO:
        for (int i = 2; i < 60; i++) {
         // 枚举 2~59 进制，并判断是否超范围
            if (match(m, i)) result.push_back(i);
        }
        if (result.empty()) {
                  // 如果全部不可用，返回 0
            result.push_back(0);
            return result;
        }
        if (match(m, 60)) {
            // 如果 60 进制都可以用，证明有无数种可能，返回 -1
            result.clear();
            result.push_back(-1);
            return result;
        }
        return result;
    }
    
    int main() {
        
    
        std::string m;
    
        getline(std::cin, m);;
    
        std::vector<int> result = solution(m);
    
    
        for (auto it = result.begin(); it != result.end(); ++it) {
        
            std::cout << *it << " ";
        }
        std::cout << std::endl;
    
    
        return 0;
    }