Lutece 2146 密码

题目链接: 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;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注