http://codeforces.com/contest/489/problem/B
二分匹配模板题
1 public class Main { 2 static final int maxn = 2000; 3 static int n, m; 4 static int[] a = new int[maxn]; 5 static int[] b = new int[maxn]; 6 static int[] c = new int[maxn]; 7 static int[] vis = new int[maxn]; 8 9 public static void main(String[] args) { 10 Scanner io = new Scanner(System.in); 11 n = io.nextInt(); 12 for (int i = 0; i < n; i++) a[i] = io.nextInt(); 13 14 m = io.nextInt(); 15 Arrays.fill(c, -1); 16 int ans = 0; 17 for (int i = 0; i < m; i++) b[i] = io.nextInt(); 18 for (int i = 0; i < n; i++) { 19 Arrays.fill(vis, 0); 20 match(i); 21 } 22 for (int i = 0; i < m; i++) if (c[i] != -1) ans++; 23 System.out.println(ans); 24 } 25 26 static boolean match(int i) { 27 //递归不走回头路,针对的是自己这一列,所以放在最前面 28 if (vis[i] == 1) return false; 29 vis[i] = 1; 30 for (int j = 0; j < m; j++) { 31 if (Math.abs(b[j] - a[i]) <= 1 && (c[j] == -1 || match(c[j]))) { 32 c[j] = i; 33 return true; 34 } 35 } 36 return false; 37 } 38 }