ABC221———— C - Select Mul 题解

· · 个人记录

这道题花的时间挺长的，但实际思路难度大概也就较难的橙题左右。。

当然，如果会next_permutation的话会容易许多

具体看下面吧

————————————————

题面在此

这道题一开始的时候以为切割后的数在原数列中必须相邻，导致WA了一次，结果实际没什么限制，只需让原数列排列组合并切割后的数的乘积最大即可

（什么你说原题中切割后的数的开头数字不能是0？放心对正确答案没影响，简单证明即可）

而且原题中保证序列中至少有两个非零的数，故不需要再特判直接写即可

————我是分割线————

那么如何能找到我们需要的正解呢？毕竟对数列的所有数排列的话情况很多，手动一个个提取数是不可能的，循环写起来也很麻烦

这里就需要运用到一个STL： next_permutation

详细介绍在上面了，因为博主懒 (实际是不会)就不过多讲了。

简单的说，next_permutation可以使你的一段序列自动发生全排列

转换的原则可以这样理解：对一段序列a，当下标i递增时先有证a[i] (new)>=a[i] (old) ,当第一次出现 a[i] (new)>a[i] (old) 时可以不再满足上述条件（当然，old和new都是原序列a里的数）

由上，我们可以得知，next_eprmutation是有终止条件的

————我也是分割线————

知道如何求正解以及工具的用法，我们便可以开始敲代码了

以下是自己的代码，官方题解在此

#include<bits/stdc++.h>
#define MAXN 1000001
#define ll long long
using namespace std;
char s[MAXN];
ll t[MAXN];
ll l,ans=0;
signed main()
{
    scanf("%s",(s+1));
    l=strlen(s+1);
    for(int i=1;i<=l;i++)
        t[i]=(s[i]-'0');
    sort(t+1,t+l+1);
   //这里必须有一个sort，原因见上文next_permutation的解释
    do
    {
        for(int i=2;i<=l;i++)
        {
            ll a=0,b=0;
            for(int j=1;j<i;j++)
                a=a*10+t[j];
            for(int j=i;j<=l;j++)
                b=b*10+t[j];
            ans=max(a*b,ans);
        }
    }while(next_permutation(t+1,t+l+1));
    cout<<ans;
    return 0;
}