题目链接: https://acm.uestc.edu.cn/problem/mi-ma-1/description
分析:
既然要求最大的数,那么越大的数字放在前面这个数当然越大。
从某种层面上来说,这是一个贪心,即每次在剩余的数字中挑选最大的。
但是也不能随便挑,要保证挑选完这个后面的数字还足够。
采取vector数组的方法读入。
这样子读入的方式有一个好处,就是vector里存储的是这个数字在整个字符串中的位置,而且是有序的。
有序的数组,就可以使用二分查找来查找值。
首先声明当前位置的变量,以及所有vector的末尾迭代器。
使用k作为最外层循环,防止k=0对结果产生影响。
接下来,从大的数字往小的数字挑,使用二分查找寻找当前位置及之后能不能找到该数字,如果能找到,且剩余的数字多于还要挑选的,则输出并更新当前位置。如此循环,就能找到最大的数。
最终的复杂度,应该不会超过O(16KlogN)。实际上比这个小得多。
代码:
#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); int n, k; char qwe[16] = {'f','e','d','c','b','a','9','8','7','6','5','4','3','2','1','0'}; char linshi; while (cin>>n>>k) { vector<int> s[16]; for (int i = 0; i < n; ++i) { cin >> linshi; switch (linshi) { case 'f': s[0].push_back(i); break; case 'e': s[1].push_back(i); break; case 'd': s[2].push_back(i); break; case 'c': s[3].push_back(i); break; case 'b': s[4].push_back(i); break; case 'a': s[5].push_back(i); break; case '9': s[6].push_back(i); break; case '8': s[7].push_back(i); break; case '7': s[8].push_back(i); break; case '6': s[9].push_back(i); break; case '5': s[10].push_back(i); break; case '4': s[11].push_back(i); break; case '3': s[12].push_back(i); break; case '2': s[13].push_back(i); break; case '1': s[14].push_back(i); break; case '0': s[15].push_back(i); break; } } int now = 0; vector<int>::iterator it1, it2[16]; for (int j = 0; j < 16; ++j) { it2[j] = s[j].end(); } for (int i = 0; i < k; ++i) { for (int j = 0; j < 16; ++j) { it1=lower_bound(s[j].begin(), s[j].end(),now); if (it1 != it2[j] && *it1+ k - i <= n) { cout << qwe[j]; now = *it1+1; break; } } } cout << endl; } return 0; }