POJ2718
POJ2718
全列挙の練習です。 この問題は各データセット内の入力の回数が与えられていないため、入力のところで無限に時間を食いました。 結局、iostreamを使用して、空白を削除しました。
最初は入力されたデータセットをグループに分け、その中で並び替えをして最小差となるようにコードを書いてましたが、友達からnext_permutationの存在を聞いたので使ってみました。(蟻本にも書いてあったような。。。)
stringでデータを取得して、ヌル文字'\0'を区切りにすることで二つのグループを作成して最小の差を求めようとしました。
結果、時間制限オーバーでした。。。
次に各グループの桁数の差を0か1の時のみ処理するようにしました。 が、これも時間制限オーバーでした。。。
結局、時間内に処理が終了せず、今回は諦めちゃいました。。。 どなたか、改善点を教えていただけると嬉しいです。。。
以下、コードです。
#include <stdio.h> #include <iostream> #include <algorithm> #include <stdlib.h> #include <cstdlib> #include <string.h> int n; int digits[10]; std::string p; char perm[12]; int tmp; int j = 0; size_t c; int l_int; int r_int; int min; int answer[1000]; void init(){ for(int i = 0; i < 10; i++){ perm[i] = '\0'; } } int solve(){ min = 99999999; do{ if(strlen(&perm[0]) == j / 2){ l_int = atoi(&perm[0]); r_int = atoi(strchr(perm, '\0') + 1); if(min > abs(l_int - r_int)) min = abs(l_int - r_int); } }while(std::next_permutation(perm, perm + j + 1)); return min; } int main(){ scanf("%d\n", &n); for(int i = 0; i < n; i++){ init(); j = 0; getline(std::cin, p); while((c = p.find_first_of(" ")) != std::string::npos){ p.erase(c,1); j++; } j++; for(int k = 0; k < j; k++){ perm[k] = p[k]; } answer[i] = solve(); } for(int i = 0; i < n; i++) printf("%d\n", answer[i]); return 0; }