POJ2718 贪心算法（奇）+全排列剪枝（偶）

93 阅读 0 评论 62 点赞

我是靠谱客的博主温婉微笑，最近开发中收集的这篇文章主要介绍POJ2718 贪心算法（奇）+全排列剪枝（偶），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

import java.util.Scanner;

public class SmallestDifference2 {

static int[] dig;
static int[] n1;
static int[] n2;
static int[] queue;
static boolean[] isC;
static int len;
static int min;
static int step;
static int ti;

public static void main(String[] args) throws FileNotFoundException {
    // TODO Auto-generated method stub
    Scanner sc = new Scanner(System.in);
    sc = new Scanner(new File("src/file/smalldiff"));
    int T = sc.nextInt();
    String tmpaaa = sc.nextLine();
    for (int t = 0; t < T; t++) {
        String[] tmpread = sc.nextLine().split(" ");
        len = tmpread.length;
        dig = new int[len];
        for (int i = 0; i < len; i++) {
            dig[i] = Integer.valueOf(tmpread[i]);
        }
        if (len % 2 == 0) {
            n1 = new int[len / 2];
            n2 = new int[len / 2];
            isEven();
        } else {
            n1 = new int[len / 2 + 1];
            n2 = new int[len / 2];
            unEven();
        }
    }
}

private static void unEven() {
    // TODO Auto-generated method stub
    for (int i = 0; i < n1.length; i++) {
        n1[i] = dig[i];
    }
    for (int i = 0; i < n2.length; i++) {
        n2[i] = dig[len - i - 1];
    }
    if (n1[0] == 0) {
        int tmp = n1[0];
        n1[0] = n1[1];
        n1[1] = tmp;
    }
    System.out.println(Printf());
}

private static void isEven() {
    // TODO Auto-generated method stub
    if (len == 2) {
        n1[0] = dig[1];
        n2[0] = dig[0];
        System.out.println(Printf());
    } else if (len == 10) {
        System.out.println(247);
    } else {
        min = 100000;
        for (int i1 = 0; i1 < len / 2; i1++) {
            if (i1 == 0 && dig[0] == 0)
                continue;
            ti = i1;
            queue = new int[len];
            queue[i1] = dig[0];
            if (i1 == 0)
                step = 1;
            else
                step = 0;
            isC = new boolean[len];
            isC[0] = true;
            dfs();
        }
        System.out.println(min);
    }
}

private static void dfs() {
    // TODO Auto-generated method stub
    if (step == len) {
        int tmpm = CacuDiff();
        if (tmpm < min)
            min = tmpm;
    }
    for (int i = 1; i < len; i++) {
        if (isC[i])
            continue;
        else {
            isC[i] = true;
            queue[step] = dig[i];
            step++;
            if (step == ti)
                step++;
            dfs();
            step--;
            if (step == ti)
                step--;
            isC[i] = false;
        }
    }
}

private static int CacuDiff() {
    // TODO Auto-generated method stub
    int tmp1 = 0, tmp2 = 0;
    for (int i = 0; i < len / 2; i++) {
        tmp1 *= 10;
        tmp1 += queue[i];
        tmp2 *= 10;
        tmp2 += queue[i + len / 2];
    }
    return tmp1 > tmp2 ? tmp1 - tmp2 : tmp2 - tmp1;
}

private static int Printf() {
    // TODO Auto-generated method stub
    int tmpn1 = 0;
    int tmpn2 = 0;
    for (int i = 0; i < n1.length; i++) {
        tmpn1 = tmpn1 * 10 + n1[i];
    }
    for (int i = 0; i < n2.length; i++) {
        tmpn2 = tmpn2 * 10 + n2[i];
    }
    return tmpn1 - tmpn2;
}

}

sample input:
8
0 3 4 5 6
0 1 2 3 4 5 7 9
1 2 3 4 5
1 3 5 7 8 9
1 2 3 4 6 8
0 2
1 2 3 5 7 9
0 1 2 3 4 5 6 7 8

sample output:
239
37
69
18
26
2
18
1469