CodeForces - 797C Minimal string （贪心）

本文主要是介绍CodeForces - 797C Minimal string （贪心），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意:给出string s长度<=1e5, op1:把s的第一个字符移动到t末尾.op2:把t最后一个字符移到u末尾,求u能得到的最小字典序?
思路：
用逆序维护一个数组Min，Min是用来表示其元素后边最小的字符，用Min是用来跟栈顶元素比较，如果栈顶元素小于等于的话就输出栈顶元素，继续用栈顶元素跟Min比较，直到不符合条件为止 。
同时每个字符都在操作结束后入栈。

#include<stdio.h>
#include<string.h>
#include<stack>
#include<algorithm>
using namespace std;
const int MAXN = 1e5+7;
char s[MAXN];
int Min[MAXN];
int main()
{while(~scanf("%s",&s)){int n=strlen(s);memset(Min,0,sizeof(Min));for(int i=n-1;i>=0;i--){int a=s[i];if(i==n-1) Min[i]=a;else Min[i]=min(Min[i+1],a);//min只能是两个类型比较 }stack<char>sta;for(int i=0;i<n;i++){if(sta.empty())sta.push(s[i]);else{while(!sta.empty()) //这个栈的判断必须写，因为不写就会出现栈顶元素底下的元素比要加入的元素小却没被输出的情况 {char c=sta.top();if(c<=Min[i]){printf("%c",c);sta.pop();}elsebreak;}sta.push(s[i]);}}while(!sta.empty()){char c=sta.top();printf("%c",c);sta.pop();}printf("\n");}
} 

这篇关于CodeForces - 797C Minimal string （贪心）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---