富途Web后台开发一面面经

牛客35817196号：贪心 可以通过有限次的分组和重排，使得书籍编号有序。 首先，需要将书籍按照编号从小到大排序，同时记录每本书原来的位置。 排序后，遍历排序后的数组，检查相邻两本书的原始位置是否连续。如果不连续，说明这里必须要进行一次分组。 统计需要分组的次数，如果这个次数不超过给定的 ，那么就可以实现目标。 #include <iostream> (30316)#include <vector> #include <algorithm> using namespace std; void solve() { int n, k; cin >> n >> k; vector<pair<long long, int>> books(n); for (int i = 0; i < n; i++) { cin >> books[i].first; books[i].second = i; } // 按编号排序 sort(books.begin(), books.end()); int groups = 1; for (int i = 1; i < n; i++) { // 如果相邻两本书的原始位置不连续，需要增加一个分组 if (books[i].second - books[i-1].second != 1) { groups++; } } // 如果需要的分组数不超过k，则可以实现目标 cout << (groups <= k ? "True" : "False") << endl; } int main() { int t; cin >> t; while (t--) { solve(); } return 0; }