首页 > 代码库 > 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; }
1097 拼成最小的数 贪心排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。