題目描述：
Description
Furik loves math lessons very much, so he doesn't attend them, unlike Rubik. But now Furik wants to get a good mark for math. For that Ms. Ivanova, his math teacher, gave him a new task. Furik solved the task immediately. Can you?
You are given a set of digits, your task is to find the maximum integer that you can make from these digits. The made number must be divisible by 2, 3, 5 without a residue. It is permitted to use not all digits from the set, it is forbidden to use leading zeroes.
Each digit is allowed to occur in the number the same number of times it occurs in the set.
Input
A single line contains a single integer n(1?≤?n?≤?100000) — the number of digits in the set. The second line contains n digits, the digits are separated by a single space.
Output
On a single line print the answer to the problem. If such number does not exist, then you should print -1.
Sample Input
Input1 0Output
0Input
11 3 4 5 4 5 3 5 3 4 4 0Output
5554443330Input
8 3 2 5 1 5 2 2 3Output
-1
就是給你n個數，讓你求由這n個數組成的，能被2,3,5整除的的最大的數。
思路：
這道題本來是用來練手速的，沒想到一做就是一個下午。最後還是看了BMan的代碼才勉強AC的，不過看了BMan的代碼之後，真的學到了很多的東西！例如，學到了CF裡面有一個ONLINE_JUDGE的宏變量，可以利用條件編譯來方便測設與提交！最重要的是學到了一個思路，那就是預處理的優美之處！
具體做法是：因為答案要能被3整除，所以各位數之和必須為3的倍數！如果是，直接輸出；否則的話有兩種可能：
1. sum % 3 == 1 這種情況只需在數列中找到一個num[i] % 3 == 1 的數去掉就可以咯，如果沒有就找兩個num[] % 3 == 2 去掉就可以了！
2..sum % 3 == 2,這種情況跟上一種是基本一致的，就不在贅述了！
這個題目有一個易錯點，就是在判斷前導0，BMan給出了一個很強大的做法，具體的做法請看代碼實現：
#include#include #include #include #include #include #include #define N 1000010 using namespace std; void debug() { #ifdef ONLINE_JUDGE #else freopen( "in.txt", "r", stdin ); #endif // JUDGE_ONLINE } int main() { debug(); //freopen( "in.txt", "r", stdin ); int n; while( scanf( "%d", &n ) != EOF ) { int num[N] = {0}; int vis[N]; int sum = 0; memset( vis, 0, sizeof( vis ) ); for( int i = 0; i < n; i++ ) { scanf( "%d", &num[i] ); sum += num[i]; } sort( num, num + n, greater () ); if( sum % 3 == 1 ) { for( int i = n-1; i >= 0; i-- ) { if( num[i] % 3 == 1 ) { vis[i] = 1; sum -= num[i]; break; } } int two = 0; if( sum % 3 == 1 )//說明找不到num[i] % 3 == 1 的num { for( int i = n-1; i >= 0; i-- ) { if( num[i] % 3 == 2 ) { vis[i] = 1; if( ++two >= 2 ) { break; } } } if( two != 2 ) { printf( "-1\n" ); continue; } } } if( sum % 3 == 2 ) { for( int i = n-1; i >= 0; i-- ) { if( num[i] % 3 == 2 ) { vis[i] = 1; sum -= num[i]; break; } } int one = 0; if( sum % 3 == 2 ) { for( int i = n-1; i >= 0; i-- ) { if( num[i] % 3 == 1 ) { vis[i] = 1; if( ++one >= 2 ) { break; } } } if( one != 2 ) { printf( "-1\n" ); continue; } } } int cnt = 0; for( int i = 0; i < n; i++ ) { if( !vis[i] ) { num[cnt++] = num[i]; } } n = cnt; if( n == 0 || num[n-1] != 0 ) { printf( "-1" ); } else { int i = 0; while( i < n - 1 && num[i] == 0 )//判斷前導0，如果一開始num[0]就等於0的話，由於已經進行了降序的排序，所以後面一定是0，這樣的話與後面的代碼結合就能夠保證 //前導0的只輸出一個0 { i++; } for( ; i < n; i++ ) { printf( "%d", num[i] ); } } putchar( 10 ); } return 0; }
One Day One Step！
