Stars
这里用尺取法
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.io.PrintWriter; import java.io.StreamTokenizer; public class A { static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out)); public static int nextInt() throws IOException { in.nextToken(); return (int) in.nval; } public static String next() throws IOException { in.nextToken(); return (String) in.sval; } static int v[] = new int[405]; // 获取一列的星星数量 static int n, k; public static void main(String[] args) throws Exception { int T = nextInt(); while(T-->0) { n = nextInt(); k = nextInt(); int a[][] = new int[n + 1][n + 1]; int x, y; for(int i = 0; i < n; i++) { x = nextInt(); y = nextInt(); a[x][y] = 1; } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { a[i][j] += a[i][j - 1]; // 左边的积累到右边去、 } } for(int i = 1; i <= n; i++) { for(int j = 1; j <= n; j++) { a[i][j] += a[i - 1][j]; // 上面的积累到下面去、、 } } int ans = n * n; // 两额循环，遍历所有的行（选两行） for(int i = 0; i <= n; i++) { for(int j = i + 1; j <= n; j++) { ans = Math.min(ans, (j - i) * cal(a, i, j)); } } out.println(ans); out.flush(); } } public static int cal(int arr[][], int l, int r) { // 数组，行坐标，以及最少选几个星星、 int start = 0, end = 0; // 起点终点， （尺取法） for(int i = 0; i <= n; i++) { v[i] = arr[r][i] - arr[l][i]; // 获取一列的星星数量、、 } while(end <= n && v[end] < k) { end++; } if(end > n) { return 0x3f3f3f; // 返回一个很大的值，保证这个结果不会被选择 } int ret = end; while(end <= n) { // 得出来的就是最小的范围，且包含了至少k个星星 if(v[end] - v[start] >= k) { ret = Math.min(ret, end - start++); // 满足的话，尾巴的就++ }else { end++; // 不满足头++ } } return ret; } }