たこ焼き販売問題 - 顧客を満足させるには？ C++コードで解決

{"title":"请帮忙讲解以下题目：\n高橋君は、たこ焼きをどの順番で売るか悩んでいました。というのも、作り置きされたたこ焼きは美味しくないとわかっているので、高橋君はそのようなたこ焼きを売りたくないのですが、できたてばかり売ってしまうと売れるたこ焼きの数が減ってしまいます。\n\nまた、お客さんを待たせてばかりだと、次第にお客さんが離れてしまうだろうと高橋君は考えています。\nそこで、彼は \n\tT 秒以内に作成されたたこ焼きを売り続けることで、お客さんを捌ききれるかどうかを調べることにしました。\n\ntako焼きは \n\t1\nA1\n​ 、\n\t2\nA2\n​ 、…、\n\t\nA\nN\n​ 秒後に焼きあがります。\nお客さんは \n\t1\nB1\n​ 、\n\t2\nB2\n​ 、…、\n\t\nB\nM\n​ 秒後にやってきます。\n1\n1 人のお客さんに対して、たこ焼きを \n1\n1 つ売るとします。すべてのお客さんにたこ焼きを売れるならyes、売れないならnoを出力して下さい。\n\n入力は以下の形式で標準入力から与えられる。 > \n\tT \n\tN \n\t1\nA1 A2...... AN\nB1 B2....... BM\n1 行目に、何秒以内のたこ焼きまで売るかを表す整数T(1≦T≦100)が与えられます。\n2 行目に、高橋君が作成するたこ焼きの総数を表す整数N(1≦N≦100)が与えられます。\n3 行目に、それぞれのたこ焼きが何秒後にできるかを表す整数 Ai(1≦Ai≦100、A1≦A2≦...≦AN) が半角スペース区切りで N 個与えられます。\n4 行目に、来店するお客さんの人数を表す整数M(1≦M≦100)が与えられます。\n5 行目に、それぞれのお客さんが何秒後に来るかを表す整数 Bi(1≦Bi≦100、B1≦B2≦...≦BN)が半角スペース区切りで M 個与えられます。\nすべてのお客さんにたこ焼きをすぐ売れるならyes、売れないならnoを出力して下さい。\nまた、出力の末尾には改行を入れて下さい。\n请用C++回答内容：题目要求判断在给定时间内是否能够将所有的顾客服务完毕，如果可以则输出"yes"，否则输出"no"。\n\n算法思路：\n1. 首先，将高橋君制作的所有的たこ焼き的完成时间按照从小到大排序，将来顾客到达的时间按照从小到大排序。\n2. 使用两个指针，一个指向たこ焼き的完成时间列表，一个指向顾客到达时间列表。\n3. 判断当前时间是否小于给定的时间T，并且还有剩余的たこ焼き和顾客未处理。\n4. 如果当前时间小于给定的时间T，则将たこ焼き的完成时间和顾客到达时间进行比较：\n a. 如果たこ焼き的完成时间小于等于顾客到达时间，则将该たこ焼き卖给该顾客，并将两个指针都向后移动一位。\n b. 如果たこ焼き的完成时间大于顾客到达时间，则不能将该たこ焼き卖给该顾客，将指向たこ焼き的指针向后移动一位。\n5. 重复步骤4直到所有的たこ焼き和顾客都处理完毕。\n6. 判断是否所有的顾客都被服务完毕，如果是则输出"yes"，否则输出"no"。\n\nC++代码示例：\n\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nint main() {\n int T, N, M;\n cin >> T >> N;\n vector<int> tako(N);\n for (int i = 0; i < N; i++) {\n cin >> tako[i];\n }\n cin >> M;\n vector<int> customer(M);\n for (int i = 0; i < M; i++) {\n cin >> customer[i];\n }\n\n sort(tako.begin(), tako.end());\n sort(customer.begin(), customer.end());\n\n int takoIdx = 0, customerIdx = 0;\n while (takoIdx < N && customerIdx < M && tako[takoIdx] <= T) {\n if (tako[takoIdx] <= customer[customerIdx]) {\n takoIdx++;\n customerIdx++;\n } else {\n takoIdx++;\n }\n }\n\n if (customerIdx == M) {\n cout << "yes" << endl;\n } else {\n cout << "no" << endl;\n }\n\n return 0;\n}\n\n\n时间复杂度分析：\n- 排序时间复杂度为O(NlogN + MlogM)\n- 判断的时间复杂度为O(N + M)\n总的时间复杂度为O(NlogN + MlogM)。