51nod1255【贪心-栈的应用】

思路：

大体可以看到：大的越后面越好，但是首先要保证如果他对于一个比他小的字符后面存在他。

主要操作就是利用栈，每次对栈里的元素询问是否比他大，且他的后面还存在。

#include<bits/stdc++.h>

using namespace std;

char s[100010];

int len,num[27];

bool vis[27];

stack<int>q;

vector<char>xs;

int main()

{

	xs.clear();

	while(!q.empty()) q.pop();

	memset(num,0,sizeof(num));

	scanf("%s",s);

	len=strlen(s);

	int x;

	for(int i=0;i<len;i++)

	{

		x=s[i]-'a';

		num[x]++;

	}

	memset(vis,false,sizeof(vis));

	for(int i=0;i<len;i++)

	{

		x=s[i]-'a';

		if(vis[x])

		{

			num[x]--;

			continue;

		}

		if(q.empty())

		{

			q.push(x);

			vis[x]=true;

			num[x]--;

		}

		else

		{

			while(!q.empty()&&q.top()>x)

			{

				if(num[q.top()])

				{

					vis[q.top()]=false;

					q.pop();

				}

				else

					break;

			}

			q.push(x);

			vis[x]=true;

			num[x]--;

		}

	}

	while(!q.empty())

	{

		xs.push_back(q.top()+'a');

		q.pop();

	}

	int sz=xs.size();

	for(int i=sz-1;i>=0;i--)

		printf("%c",xs[i]);

	return 0;

}

巴特西

51nod1255【贪心-栈的应用】

最新文章

热门文章