牛客多校第九场 I-The Crime-solving Plan of Groundhog(思维+高精）

题意

• 链接：The Crime-solving Plan of Groundhog
• 给出n个0-9的数，求由这n个数组成的两个的成绩最小

解题思路

• 把当前的数字拆成4个数 ?, ?, ?, ?(? ≤ ? ≤ ? ≤ ?) ,那么我们有两种决策：两位数×两位数，或者三位数×一位数。
  10? + ? ? 10? + ? = 100?? + 10?? + 10?? + ??
  100? + 10? + ? ? ? = 100?? + 10?? + ?? < 10? + ? ? 10? + ?
• 同理类推，可以证明留一个最小的正整数作为第一个数，剩下的所有数字排成最小的数作为第二个数时，答案取到最
  小值。
• 所以我们只需要把n个数排序，然后把前两个0与最小的两个正整数交换，则答案即a[0]*(a[1]……a[n-1]),用高精处理

代码

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1e5+5;
typedef long long ll;
int t,n,ans,a[maxn];
int main()
{scanf("%d",&t);while(t--){scanf("%d",&n);for(int i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);int pos=0;while(a[pos]==0)pos++;if(pos>=0)swap(a[0],a[pos]);if(pos>=1)swap(a[1],a[pos+1]);for(int i=1;i<n;i++)a[i]*=a[0];for(int i=n-1;i>1;i--)a[i-1]+=a[i]/10,a[i]%=10;for(int i=1;i<n;i++)printf("%d",a[i]);printf("\n");}return 0;
}