C++ 寻找最大对数对数量 - 算法详解与实现

"C++ 寻找最大对数对数量 - 算法详解与实现"\n\n本文讲解如何使用 C++ 语言解决"寻找最大对数对数量"问题，并提供详细的算法思路和代码实现。\n\n问题描述：\n给定 N 对数，要求找出最多对数，并按照特定规则排序，满足 Ai > Bj 对于所有 i < j。\n\n思路：\n1. 首先按照 A 升序排序，如果 A 相等，则按照 B 降序排序，这样可以保证对于每一对 <Ai, Bj>，Ai > Bj。\n2. 然后从排序后的数对中找出最长的递增序列。\n3. 输出递增序列的长度即为极大值 K。\n\nC++实现：\ncpp\n#include <iostream>\n#include <vector>\n#include <algorithm>\nusing namespace std;\\nbool compare(pair<int, int> p1, pair<int, int> p2) {\n if (p1.first == p2.first)\n return p1.second > p2.second; // 如果 A 相等，则按照 B 降序排序\n else\n return p1.first < p2.first; // 按照 A 升序排序\n}\n\nint main() {\n int N;\n cin >> N;\n vector<pair<int, int>> nums(N);\n for (int i = 0; i < N; i++) {\n cin >> nums[i].first >> nums[i].second;\n }\n sort(nums.begin(), nums.end(), compare); // 排序\n vector<int> dp(N, 1); // dp[i]表示以第 i 个数对结尾的最长递增序列的长度\n int maxLen = 1; // 最长递增序列的长度\n for (int i = 1; i < N; i++) {\n for (int j = 0; j < i; j++) {\n if (nums[i].second > nums[j].second) {\n dp[i] = max(dp[i], dp[j] + 1);\n }\n }\n maxLen = max(maxLen, dp[i]);\n }\n cout << maxLen << endl;\n return 0;\n}\n