CodeForces 124B Permutations

开发者伊糖技术 2022年11月9日

0 收藏 789 点赞 3,747 浏览 1536 个字

http://codeforces.com/problemset/problem/124/B

Description

You are given nk-digit integers. You have to rearrange the digits in the integers so that the difference between the largest and the smallest number was minimum. Digits should be rearranged by the same rule in all integers.

Input

The first line contains integers n and k — the number and digit capacity of numbers correspondingly (1 ≤ n, k ≤ 8). Next n lines contain k-digit positive integers. Leading zeroes are allowed both in the initial integers and the integers resulting from the rearranging of digits.

Output

Print a single number: the minimally possible difference between the largest and the smallest number after the digits are rearranged in all integers by the same rule.

Sample Input

Input

Output

Input

Output

Input

Output

20522
题目大意：给你n个长度为m的数字串，你可以任意调换第i列和第j列的数字，得到新的n个数，求出最大值减最小值最小的情况，输出二者的插值。
数据不大，1 ≤ n, k ≤ 8，用全排列就ok。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;long long n,m,ma,mi,t,b[110000][10],s,flag[10],temp[10],ans;
char a[10][10];
void dfs(int k)//将k的全排列算出来，存在b数组中。
{
     if (k>m)
     {
             for (int i=1;i<=m;i++)
             b[s][i]=temp[i];
              s++;
              return;
     }
     for (int i=1;i<=m;i++)
     {
         if (!flag[i])
         {
              temp[k]=i;
              flag[i]=true;
              dfs(k+1);
              flag[i]=false;
         }
     }
}
int main()
{    while (cin>>n>>m)
    {
          for (int i=1;i<=n;i++)
          cin>>a[i];
          s=0;
          memset(flag,false,sizeof(flag));
          dfs(1);
          ans=999999999;
          for (int p=0;p<s;p++)//求出每种全排列下的最大值和最小值，计算二者只差。
          {
              ma=-1;
              mi=999999999;
              for (int i=1;i<=n;i++)
              {
                  long long temp=0;
                  for (int j=0;j<m;j++)
                  {
                      temp=temp*10+a[i][b[p][j+1]-1]-48;
                  }
                  if (ma<temp)
                  ma=temp;
                  if (mi>temp)
                  mi=temp;
              }
              if (ans>ma-mi)
              ans=ma-mi;
          }
          cout <<ans<<endl;
    }
    return 0;
}