C++ 解题：ABC005C - 美味的章鱼烧的销售方式

题目描述

高橋君正在烦恼要如何安排章鱼烧的销售顺序。他明白，放久了之后章鱼烧的口感会变差，所以他不想卖那些放久的章鱼烧。然而，如果只卖刚出炉的章鱼烧，会导致卖出的章鱼烧数量减少。

另外，如果让顾客一直等待，顾客可能会离开。

因此，他决定通过在 $T$ 秒内继续销售制作的章鱼烧，来调查是否能销售完顾客。

章鱼烧在 $A1$、$A2$、…、$AN$ 秒后烤好。

顾客 $B1$，$B2$，…，$BM$ 秒后就来。

每一个客人只能买一个章鱼烧。如果所有的客人都能买到章鱼烧的话，输出 'yes'；反之，输出 'no'。

代码实现

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int T, N, M;
    cin >> T >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    cin >> M;
    vector<int> B(M);
    for (int i = 0; i < M; i++) {
        cin >> B[i];
    }

    int j = 0;
    for (int i = 0; i < M; i++) {
        if (B[i] < A[j] || B[i] > A[j] + T) {
            cout << "no" << endl;
            return 0;
        }
        while (j < N && A[j] + T < B[i]) {
            j++;
        }
        if (j == N) {
            cout << "no" << endl;
            return 0;
        }
        j++;
    }

    cout << "yes" << endl;

    return 0;
}

代码解析

首先读取输入数据，包括：
- T: 销售时间限制
- N: 章鱼烧数量
- A: 每个章鱼烧的制作时间
- M: 顾客数量
- B: 每个顾客的到达时间
使用两个指针 i 和 j，分别指向当前顾客和当前可销售的章鱼烧。
遍历顾客列表，对于每个顾客：
- 如果顾客到达时间早于当前可销售的章鱼烧的制作时间，或者顾客到达时间晚于当前可销售的章鱼烧的制作时间加 T，则说明无法满足该顾客的需求，输出 no 并结束程序。
- 否则，判断当前可销售的章鱼烧是否能满足该顾客的需求，如果不能，则将 j 指针指向下一个可销售的章鱼烧，直到找到合适的章鱼烧或遍历完所有章鱼烧。
- 如果遍历完所有章鱼烧仍然没有找到合适的章鱼烧，则说明无法满足该顾客的需求，输出 no 并结束程序。
- 如果找到合适的章鱼烧，则将 j 指针指向下一个章鱼烧，继续处理下一个顾客。
如果所有顾客都能被满足，则输出 yes。

总结

本代码使用贪心算法，通过不断寻找最合适的章鱼烧来满足顾客的需求。该算法效率较高，能够在较短的时间内解决问题。