uva-1368(贪心,字符串模拟)

uva--1368(贪心,字符串模拟)

点击打开链接

该题是一个带有贪心思想的字符串模拟题，题目给定m个长度为n的字符串，让你求一个长度为n的字符串，使得该字符串与这m个字符串对应位置的字符不同的个数和最小。

要使对应位置不同字符最少，则该字符串每个字符优先选择该位置出现次数多的字符，若次数相同则选择字典序更小的字符。

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <math.h>
#include <vector>
#include <set>
#define from(i,a,n)   for(int i=a;i<n;i++)
#define refrom(i,n,a) for(int i=n;i>=a;i--)
#define EPS 1e-10
#define mod 1000000007
using namespace std;

const double INF=0x3f3f3f3f;
const int MAX =1000+10;
int m,n,pos,num;
char s[52][MAX],s1[MAX],s2[51];//s1用来记录字典序最小的符合条件的序列,s2用来处理每一个位置的字符
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>m>>n;
        int dis=0;
        memset(s1,0,sizeof(s1));
        num=0;
        //getchar();
        from(i,0,m)
        cin>>s[i];
        from(i,0,n)
        {
            pos=0;
            int maxlen=-INF,cnt=1;
            char c;
            from(j,0,m)
            s2[pos++]=s[j][i];//将第i个位置的所有字符取出
            sort(s2,s2+pos);//按升序排序,那么最先找到的一定是字典序小的字符
            c=s2[0];
            from(j,1,pos)
            {
                if(s2[j]==s2[j-1]) cnt++;
                else
                {
                    if(maxlen<cnt) {maxlen=cnt;c=s2[j-1];}//只有在字符出现次数个数小时才改变，否则不改变，这样保证了最小字典序的条件
                    cnt=1;
                }
            }
            if(maxlen<cnt) {maxlen=cnt;c=s2[pos-1];}//跳出循环后还要判断一次
            s1[num++]=c;
            dis+=(m-maxlen);//总共字符个数减去最大出现次数就是该位置字符对于总的距离的贡献
            }
            cout<<s1<<endl<<dis<<endl;
    }
    return 0;
}