sicily 1198 Substring 解题总结

summary

:

一看题目，总觉得直接sort就可以A了，但是交上去就是WA，无奈之下，只好google一下 偷看一下人家的分析。。。。。。。果然是有特殊情况！比如 dc dcc，直接sort，得到 的是dcdcc,而正确答案是dccdc，于是要自己写比较函数了！！

代码:

#include <iostream>
#include <string>

using namespace std;

bool cmp(string s1,string s2)
{
    int i,j;
    for(i = j = 0; i < s1.size() && j < s2.size(); i++,j++){
        if(s1[i] > s2[j])
            return false;
        else if(s1[i] < s2[j])
            return true;
    }
    if(i == s1.size() && j == s2.size())
        return false;
    else if(i == s1.size() || j == s2.size()){
        if(s1+s2 < s2+s1)
            return true;
        else
            return false;
    }
}

int main()
{
    int t,n,i,j,k;
    string s[100];

    cin >> t;

    while(t--){
        cin >> n; 
        for(i = 0; i < n; i++){
            cin >> s[i];
        }
        for(i = 0; i < n - 1; i++){
            k = i;
            for(j = i + 1; j < n; j++){
                if(cmp(s[j],s[k]))
                    k = j;
            }
            if(k != i){
                string temp = s[i];
                s[i] = s[k];
                s[k] = temp;
            }
        }
        for(i = 0; i < n; i++){
            cout << s[i];
        }
        cout << endl;
    }
    return 0;
}