[求助]有一个长度为n的字符串s，你可以删除其中的m个字符，使剩余字符串的字典序最小，输出这个字符串。 - 编程论坛

#2

D22845814702019-12-17 20:56

虽然我努力的帮你看，但我现在还是不懂

#3

bcbbcclbbc2019-12-18 10:11

解答什么，你那里不懂，请陈述，光贴题目，无法得知你的疑问

#4

rjsp2019-12-18 11:14

伪代码大约是
foo( s, n, m )
{
    m = 最小值(n,m)
    if( m == 0 )
        return s;

    minchar = 在 s 的前 m+1 个字符中的最小值
    因为 s 的前 m+1 个字符中的可能有多个同时最小
    所以得递归调用 foo( s+i, n-i, m-i )，其中 i 是最小字符的下标
    选出其中最小的那个
}

#5

rjsp2019-12-18 13:16

手上没有编译器，用 https:// 编译了一下，没法保证正确，仅供参考

程序代码：

#include <stdio.h>
#include <string.h>

void foo( char* s, unsigned n, unsigned m )
{
    m = m<=n?m:n;
    if( m == 0 )
        return;

    char minchar = s[0];
    for( unsigned i=1; i!=m+1; ++i )
        minchar = minchar<=s[i]?minchar:s[i];

    char s_min[106];
    strcpy( s_min, s );
    for( unsigned i=0; i!=m+1; ++i )
    {
        if( minchar != s[i] )
            continue;

        char s2[106];
        strcpy( s2, s+i );
        foo( s2+1, n-i-1, m-i );
        if( strcmp(s2,s_min) < 0 )
            strcpy( s_min, s2 );
    }
    strcpy( s, s_min );
}

int main( void )
{
    unsigned t;
    scanf( "%u", &t );
    while( t-- )
    {
        unsigned n, m; char s[106];
        scanf( "%u%u%s", &n, &m, s );
        foo( s, n, m );
        puts( s );
    }
}

#6

Sky_2019-12-18 20:07

回复 5楼 rjsp

谢谢大佬解答，不过提交的时候显示运行错误
还有，目前还有点懵，我会再仔细理解一下你的代码思路
谢谢大佬啦

[此贴子已经被作者于2019-12-18 20:09编辑过]

#7

rjsp2019-12-19 08:56

以下是引用Sky_在2019-12-18 20:07:24的发言：

谢谢大佬解答，不过提交的时候显示运行错误
还有，目前还有点懵，我会再仔细理解一下你的代码思路
谢谢大佬啦

要么一个个的删除，遍历，如果当前字符大于下一个字符，那就将当前字符删除；每次删除一个后，回退一格从新开始。

#8

rjsp2019-12-19 09:07

回复 6楼 Sky_

试试吧，不行我再改

程序代码：

#include <stdio.h>
#include <string.h>

void foo( char* s, unsigned n, unsigned m )
{
    m = m<=n?m:n;

    for( size_t i=0; i!=n && m!=0; )
    {
        if( s[i] > s[i+1] )
        {
            memmove( s+i, s+i+1, n-i );
            --m, --n;
            if( i > 0 )
                --i;
        }
        else
            ++i;
    }
}

int main( void )
{
    unsigned t;
    scanf( "%u", &t );
    while( t-- )
    {
        unsigned n, m; char s[106];
        scanf( "%u%u%s", &n, &m, s );
        foo( s, n, m );
        puts( s );
    }
}

#9

Sky_2019-12-19 14:20

回复 8楼 rjsp

答案正确了
跪谢大佬