TopCoder SRM 399 Level 2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8758&rd=12171
給定N和一個(gè)整數(shù)集合a，用不屬于a的3個(gè)整數(shù)相乘得出離N最近的整數(shù)

N的范圍1～1000
從小到大3重循環(huán)就可以解
理論上的復(fù)雜度高達(dá)1000^3
如果確實(shí)算一次我的電腦要跑到6秒
不過(guò)其實(shí)當(dāng)乘積減去N已經(jīng)超過(guò)之前的差額時(shí)就可以break了
所以計(jì)算量其實(shí)很小
加上break算一次只要零點(diǎn)零幾秒
另外的陷阱是循環(huán)如果只是1～1000是不行的
有可能會(huì)用到比1000還大的因子
 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class AvoidingProduct
 8{
 9    int SIZE = 1101;
10    
11    public int[] getTriple(int[] a, int n)
12    {
13        boolean[] table = new boolean[SIZE];
14        Arrays.fill(table, true);
15        for(int i = 0  ; i < a.length ; ++ i)
16            table[a[i]] = false;
17        int x,y,z;
18        int[] ans = new int[3];
19        Arrays.fill(ans, Integer.MAX_VALUE);
20        int gap = Integer.MAX_VALUE;
21        Outer:
22        for(x = 1 ; x < SIZE; ++ x){
23            if(table[x] == false) continue;
24            for(y = 1; y < SIZE; ++ y){
25                if(table[y] == false) continue;
26                for(z = 1 ; z < SIZE; ++ z){
27                    if(table[z] == false) continue;
28                    int total = x * y * z;
29                    int sub = n - total;
30                    if(Math.abs(sub) < gap){
31                        ans[0] = x; ans[1] = y; ans[2] = z;
32                        gap = Math.abs(sub);
33                    }
34                    if(sub < 0 && Math.abs(sub) >= gap)
35                        break ;
36                }
37            }
38        }
39        return ans;
40    }
41    
42}