2014 1B A - The Repeater

domen111

Google Code Jam 2014年 Round 1B
原題(英文): https://code.google.com/codejam/contest/2994486/dashboard
TOJ(中文，難度加強): http://toj.twbbs.org/oj/pro/1/

簡化題意:
N個字串，你可以做一些操作讓他們一樣，求最小操作數。操作有:
操作有:
1.將同樣的字元複製成連續兩個。
2.將連續兩個字元合併成一個。
無法讓這些字串一樣則輸出「Fegla Won」

Input	Output
5 2 mmaw maw 2 gcj cj 3 aaabb ab aabb 2 abc abc 3 aabc abbc abcc	Case #1: 1 Case #2: Fegla Won Case #3: 3 Case #4: 0 Case #5: 3

解法:
先統計字元個數，如測資3可整理為:
a3b2
a1b1
a2b2
如此可以將題目兩操作化簡為: 可以任意加減每個字元的各數(最少減為1)
如果字元順序不一樣，則表示無法達成，輸出Fegla Won。
再來就把題目化簡成:有一些數字要對它們加減使它們相同。
例如測資3:
a有3,1,2 要使它們相同，將它們都改為2，操作數為2
b有2,1,2 要使它們相同，將它們都改為2，操作數為1
2+1=3，答案3
那麼要將它們改為多少就是一個簡單的數學問題(高一上有教)，總之就是要改成中位數。

AC code:
http://ideone.com/OZ5h5f

#include<cstdio>

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int n;

vector<char> chs[120];

vector<int> chc[120];

int cal(vector<int> &data)

{

        sort(data.begin(),data.end());

        int ans=0;

        int bb=data[data.size()/2];

        for(int i=0;i<data.size();i++)

                ans+=abs(data[i]-bb);

        return ans;

}

int solve()

{

        int t=chs[0].size();

        for(int i=1;i<n;i++)

                if(chs[i].size()!=t)

                        return -1;

        for(int i=1;i<n;i++)

                for(int j=0;j<chs[i].size();j++)

                        if(chs[i][j]!=chs[0][j])

                                return -1;

        vector<int> data;

        int ans=0;

        for(int i=0;i<chs[0].size();i++)

        {

                data.clear();

                data.resize(n);

                for(int j=0;j<n;j++)

                {

                        data[j]=chc[j][i];

                }

                ans+=cal(data);

        }

        return ans;

}

int main()

{

        int T;

        cin>>T;

        for(int no=1;no<=T;no++)

        {

                cin>>n;

                string temp;

                for(int i=0;i<n;i++){

                        chs[i].clear();

                        chc[i].clear();

                        cin>>temp;

                        chs[i].push_back(temp[0]);

                        chc[i].push_back(1);

                        for(int j=1;j<temp.size();j++)

                        {

                                if(temp[j]==chs[i].back()){

                                        chc[i].back()++;

                                }else{

                                        chs[i].push_back(temp[j]);

                                        chc[i].push_back(1);

                                }

                        }

                }

                int ans=solve();

                if(ans==-1)

                        printf("Case #%d: Fegla Won\n",no);

                else

                        printf("Case #%d: %d\n",no,ans);

        }

}

TOJ AC CODE:

#include<cstdio>

#include<iostream>

#include<vector>

#include<algorithm>

using namespace std;

int n;

vector<char> chs[3010];

vector<int> chc[3010];

int cal(vector<int> &data)

{

        sort(data.begin(),data.end());

        int ans=0;

        int bb=data[data.size()/2];

        for(int i=0;i<data.size();i++)

                ans+=abs(data[i]-bb);

        return ans;

}

int solve()

{

        int t=chs[0].size();

        for(int i=1;i<n;i++)

                if(chs[i].size()!=t)

                        return -1;

        for(int i=1;i<n;i++)

                for(int j=0;j<chs[i].size();j++)

                        if(chs[i][j]!=chs[0][j])

                                return -1;

        vector<int> data;

        int ans=0;

        for(int i=0;i<chs[0].size();i++)

        {

                data.clear();

                data.resize(n);

                for(int j=0;j<n;j++)

                {

                        data[j]=chc[j][i];

                }

                ans+=cal(data);

        }

        return ans;

}

int main()

{

        ios::sync_with_stdio(false);

        int T;

        cin>>T;

        for(int no=1;no<=T;no++)

        {

                cin>>n;

                string temp;

                for(int i=0;i<n;i++){

                        chs[i].clear();

                        chc[i].clear();

                        cin>>temp;

                        chs[i].push_back(temp[0]);

                        chc[i].push_back(1);

                        for(int j=1;j<temp.size();j++)

                        {

                                if(temp[j]==chs[i].back()){

                                        chc[i].back()++;

                                }else{

                                        chs[i].push_back(temp[j]);

                                        chc[i].push_back(1);

                                }

                        }

                }

                int ans=solve();

                if(ans==-1)

                        printf("Case #%d: Fegla Won\n",no);

                else

                        printf("Case #%d: %d\n",no,ans);

        }

}