题解 P6387 【[COCI2007-2008#4] VECI】

· · 题解

本题可采用贪心

从后往前顺序，以当前数字位置向后循环。

遇到比自己大的数字说明有解，找到符合数字的最小值并交换。

然后从尾到交换位置从小到大排序保证答案最小。

这样可以找到符合条件的最小值。

因为数据少，如果有hack数据，欢迎指出。

Code: 
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
char a[11],qwq;
int main()
{
    scanf("%s",a+1);
    int n=strlen(a+1),t=1,sum,minn=2147483647;
  //t是判断有解变量，minn是存最小值变量
    for(int i=n-1;i>=1;i--)
    {//从后往前顺序
        for(int j=i+1;j<=n;j++)
        {//以当前数字位置向后循环
            if(a[j]>a[i])
            {//比自己大的数字
                if(a[j]<minn)//判断最小值
                {
                    t=0;
                    sum=j;//储存位置
                    minn=a[j];
                }
            }
        }
        if(!t)//有解
        {
            qwq=a[i];
            a[i]=a[sum];
            a[sum]=qwq;
            sum=i;//交换
            break;
        }
    }
    if(!t)
    {
        sort(a+sum+1,a+n+1);//从小到大排序
        for(int i=1;i<=n;i++)
            printf("%c",a[i]);
    }
    else
        printf("0");
}

因为n<=6，所以 n^2的复杂度完全可以接受

小Copy宜心，大Copy伤身