競プロはじめました

競プロ初心者のブログ

POJ2718

POJ2718

2718 -- Smallest Difference

全列挙の練習です。 この問題は各データセット内の入力の回数が与えられていないため、入力のところで無限に時間を食いました。 結局、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;
}