UVa:10132 File Fragmentation

其實想明白了還是道挺簡單的題。

最大的碎片跟最小的組合中一定有原檔案。次最大和次最小的碎片的組合中也一定有原檔案。

很明顯兩個組合中相同的那個檔案就是原檔案。

因為沒有完全相同的碎片，是以即使最大的和最小的碎片都有兩個，這個思路也是完全可行的。

算是貪心吧，這是解決問題的一個很關鍵的點。

當然如果一共就兩塊碎片那就不用麻煩了，它倆的組合一定就是答案。

今天重做這道題居然一遍AC，想當時被卡了好久。。。

老師說過scanf、printf跟cin、cout混用會導緻莫名的現象，因為這裡用到了string，是以全換成cin、cout了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
bool cmp(string a,string b)
{
    return a.size()<b.size();
}
int main()
{
    int T;
    cin>>T;
    cin.ignore();
    cin.ignore();
    while(T--)
    {
        string str[150];
        int n=0;
        while(getline(cin,str[n])&&!str[n].empty())n++;
        if(n<=2)
            cout<<str[0]+str[1]<<endl;
        else
        {
        sort(str,str+n,cmp);
        string a=str[0],b=str[1],c=str[n-2],d=str[n-1];
        if(a+d==b+c||a+d==c+b) cout<<a+d<<endl;
        else if(d+a==b+c||d+a==c+b) cout<<d+a<<endl;
        else if(a+c==b+d||a+c==d+b) cout<<a+c<<endl;
        else if(c+a==b+d||c+a==d+b) cout<<c+a<<endl;
        }
        if(T) cout<<endl;
    }
    return 0;
}