K - Minimal string 以及 栈排序

原 作者 王一妃 | 发表于 | 分类于 2015级

Petya recieved a gift of a string s with length up to 105 characters for his birthday. He took two more empty strings t and u and decided to play a game. This game has two possible moves:

  • Extract the first character of s and append t with this character.
  • Extract the last character of t and append u with this character.

Petya wants to get strings s and t empty and string u lexicographically minimal.

You should write a program that will help Petya win the game.

Input

First line contains non-empty string s (1 ≤ |s| ≤ 105), consisting of lowercase English letters.

Output

Print resulting string u.

Example
Input 
cab
Output 
abc
Input 
acdb
Output 
abdc


这道题目的意思是给你一个栈让你最大可能的按字典序减小排列这个串，它规定s->t,t->u的进出方向，实际就是栈的模拟加贪心就能搞定。贪心用一个数组去维护。数组中记录数组第i位之后的最最小值。

但是我拿到这个题目的时候以为是用栈进行字符排序，于是按照要求写出来，给的第二个样例是的答案是 a b d c，我的代码答案是a b c d。甚至测了几组数据都优于答案。

有区别的原因是我认为题目给的是两个模拟栈，而从题目的答案看来，题目给定t是模拟一个栈，u是一个数组。

不过错误代码实现了栈排序的主要思路，所以贴出来吧。

AC

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<stack>
using namespace std;
char s[100005];
int a[100005];
int idx[100005];
int main()
{
    while(~scanf("%s",s))
    {
        int n=strlen(s);
        memset(idx,0,sizeof(idx));
        for(int i=0;i<n;i++)
          a[i]=s[i]-'a'+1;
        for(int i=n-1;i>=0;i--)
        {
            if(i==n-1)
              idx[i]=a[i];
            else
              idx[i]=min(idx[i+1],a[i]);
        }

        stack<char >t;

        for(int i=0;i<n;i++)
        {
            if(t.size()==0)
            {
                t.push(s[i]);
            }
            else
            {
                while(!t.empty())
                {
                    int u=t.top()-'a'+1;
                    if(u<=idx[i])
                    {
                        cout << t.top();
                        t.pop();
                    }
                    else break;
                }
                t.push(s[i]);
            }
        }
        while(!t.empty())
        {
            cout << t.top();
            t.pop();
        }
        cout << endl;
    }
}

错误

#include <iostream>
using namespace std;

int p[100005];

int main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> p[i];
    }

    int sum = 0;

    for(int i = 0; i < n; i++){
        if(p[i] % k){
            sum = sum + p[i]/k + 1;
        }
        else{
            sum = p[i]/k + sum;
        }
    }

    sum += 1;
    sum /= 2;
    cout << sum << endl;
}