程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> uva--1368(貪心,字符串模擬)

uva--1368(貪心,字符串模擬)

編輯：C++入門知識

uva--1368(貪心,字符串模擬)

該題是一個帶有貪心思想的字符串模擬題，題目給定m個長度為n的字符串，讓你求一個長度為n的字符串，使得該字符串與這m個字符串對應位置的字符不同的個數和最小。

要使對應位置不同字符最少，則該字符串每個字符優先選擇該位置出現次數多的字符，若次數相同則選擇字典序更小的字符。

代碼：

#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#define from(i,a,n)   for(int i=a;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