题目链接：http://codeforces.com/problemset/problem/381/B
题目意思：给定一个m个数的序列，需要从中组合出符合楼梯定义
的最长序列。
思路不复杂，先把输入的序列按从小到大排序，然后依次挑出不相同的数（顺挑）。接着倒序再挑出不相同的数（可以与顺挑时的数相同）。有一个要注意的地方是，挑出的那些数的位置需要标记下，防止逆挑的时候重复挑。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 const int maxn = 1e5 + 10; 9 int a[maxn], vis[maxn], res[maxn]; 10 11 int main() 12 { 13 int i, j, k, n, cnt; 14 while (scanf("%d", &n) != EOF) 15 { 16 for (i = 0; i < n; i++) 17 scanf("%d", &a[i]); 18 sort(a, a+n); 19 memset(vis, 0, sizeof(vis)); 20 21 vis[0] = 1; //第0个位置已取数 22 j = 0; 23 res[j++] = a[0]; 24 cnt = 1; 25 for (i = 0; i + 1 < n; ) 26 { 27 k = i+1; 28 while (a[k] == a[i]) // 有可能有多个a[i]的数，要跳过 29 k++; 30 if (k >= n) // 上一步中的k++有可能越界 31 break; 32 if (!vis[k]) // 防止逆挑时重复挑 33 { 34 res[j++] = a[k]; 35 vis[k] = 1; // 该位置已用 36 cnt++; 37 } 38 i = k; 39 if (a[k] == a[n-1]) // 等于最大的那个数时跳出 40 break; 41 } 42 for (i = n-1; i-1 >= 0; ) 43 { 44 k = i-1; 45 while (a[k] == a[i]) 46 k--; 47 if (k < 0) 48 break; 49 if (!vis[k]) 50 { 51 res[j++] = a[k]; 52 vis[k] = 1; // 该位置已用 53 cnt++; 54 } 55 i = k; 56 if (a[k] == a[0]) 57 break; 58 } 59 printf("%d ", cnt); 60 for (i = 0; i < j; i++) 61 printf("%d ", res[i]); 62 printf(" "); 63 } 64 return 0; 65 }
改进后的代码:
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 using namespace std; 6 7 const int maxn = 5000 + 10; 8 int cnt[maxn]; 9 10 int main() 11 { 12 int i, m, sum, tmp, maxb; 13 while (scanf("%d", &m) != EOF) 14 { 15 memset(cnt, 0, sizeof(cnt)); 16 sum = 0; 17 maxb = -1; 18 for (i = 0; i < m; i++) 19 { 20 scanf("%d", &tmp); 21 cnt[tmp]++; 22 if (cnt[tmp] == 1 || cnt[tmp] == 2) 23 sum++; 24 if (maxb < tmp) 25 maxb = tmp; 26 } 27 if (cnt[maxb] >= 2) 28 sum--; 29 printf("%d ", sum); 30 for (i = 1; i <= maxb; i++) 31 { 32 if (cnt[i]) 33 { 34 printf("%d ", i); 35 cnt[i]--; 36 } 37 } 38 for (i = maxb-1; i >= 1; i--) 39 { 40 if (cnt[i]) 41 printf("%d ", i); 42 } 43 printf(" "); 44 } 45 return 0; 46 }