PAT 解题报告 1038. Recover the Smallest Number (30)

1038. Recover the Smallest Number 题目描述:

Given a collection of number segments, you are supposed to recover the smallest number from them. For example, given {32, 321, 3214, 0229, 87}, we can recover many numbers such like 32-321-3214-0229-87 or 0229-32-87-321-3214 with respect to different orders of combinations of these segments, and the smallest number is 0229-321-3214-32-87.

给出一些数字Number的片段, 如何拼接这些片段使得最后得到的完整的字符串是所有可能的字符串里面数值最小的.

1038. Recover the Smallest Number 算法分析:

这个题目想到了应该不难, 无非是排序再加上贪心. 排序的规则要是想明白了代码非常精简, 两个片段字符串a, b 按照字典序如果a + b < b + a, 那么a应该排在前面, 否则b排在前面, 按照这样的排序然后按照顺序拼接即可. 代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>

#include <algorithm>
#include <string>
#include <vector>
#include <iomanip>

#define REP(i,n) for(int i=0;i<(n);++i)

using namespace std;

int N;
vector<string> segs;

bool cmp2(const string &a, const string &b) {
    return a+b <= b+a;
}

void gao(void) {
    sort(segs.begin(), segs.end(), cmp2);
    string res("");
    REP(i, N) res += segs[i];
    int ix = 0;
    while('0' == res[ix]) ix++;
    if(res.substr(ix).size())
        cout<<res.substr(ix)<<endl;
    else
        cout<<0<<endl;
    return ;
}

int main(void) {
    cin>>N;
    segs.resize(N);
    REP(i, N) cin>>segs[i];
    gao();
    return 0;
}

1038. Recover the Smallest Number 注意点:

第一, 注意前置000的判断. 特例是所有都是0的时候还是要输出一个0. 第二, 考虑这个例子的拼接3, 3330, 结果应该是33303而不是33330, 这个是我之前一直WA的地方. 可能你觉得不应该, 但是就是错在这么个小地方, 要注意.

Written on December 29, 2013