首页 > 代码库 > 1097 拼成最小的数 贪心排序

1097 拼成最小的数 贪心排序

http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1097

2

280

28023

 

2

280

2802

 

2

32

323231

 

首先,起始位比较小的,肯定排在前面的了。然后关键就是如何处理相同的时候,也就是32和321怎么比较。

我的做法:如果比较完后,较短的那个重头开始比较。相当于拼接了上去循环

我想到怎样做的来源是:

它肯定是开头相同的一堆放在一起的,比如开头是1的有n个,肯定是前n个开头都是1的那堆。因为这样结果更优。

那么他们两两比较时,如果有一个没了,那么就由开头的补充,然后wa后,找数据,就这样做了。

 

技术分享
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <assert.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
#include <bitset>
struct node {
    char str[22];
    int lenstr;
    bool operator < (const struct node & rhs) const {
        int now = 1;
        if (lenstr < rhs.lenstr) {
            for (int i = 1; i <= rhs.lenstr; ++i) {
                if (i > lenstr) {
                    if (str[now] != rhs.str[i]) return str[now] < rhs.str[i];
                    now++;
                    if (now > lenstr) now = 1;
                } else {
                    if (str[i] != rhs.str[i]) return str[i] < rhs.str[i];
                }
            }
            return str[now] < rhs.str[1];
        } else {
            for (int i = 1; i <= lenstr; ++i) {
                if (i > rhs.lenstr) {
                    if (str[i] != rhs.str[now]) return str[i] < rhs.str[now];
                    now++;
                    if (now > rhs.lenstr) now = 1;
                } else {
                    if (str[i] != rhs.str[i]) return str[i] < rhs.str[i];
                }
            }
            return str[1] < rhs.str[now];
        }
        return false;
    }
}a[11111];
const int maxn = 1e6 + 20;
char ans[maxn];
void work() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", a[i].str + 1);
        a[i].lenstr = strlen(a[i].str + 1);
    }
    sort(a + 1, a + 1 + n);
    int lenans = 0;
    for (int i = 1; i <= n; ++i) {
        strcpy(ans + lenans + 1, a[i].str + 1);
        lenans += a[i].lenstr;
    }
    for (int i = 1; i <= lenans; ++i) {
        printf("%c", ans[i]);
        if (i % 1000 == 0) {
            printf("\n");
        }
    }
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    work();
    return 0;
}
View Code

 

1097 拼成最小的数 贪心排序