Java运行超时

Question

我正在研究一个USACO 2016铜质二月问题3，这是我的代码，它适用于前6个测试用例。但从案件7-10，它显示超时。我想不出怎么解决这个问题。请帮帮忙！

usaco问题

这里的问题是：

农夫约翰的N头牛分别站在不同的地方(x1，y1)…(xn，yn)在他的二维农场上(1≤N≤100，而习和yi's是大小最多为B的正奇数)。FJ想要用等式x=a (a将是一个偶数整数)建立一个长的(实际上是无限长的)南北栅栏来划分他的区域，从而确保他不会通过任何奶牛的位置建造围栏。他还想建造一个长(实际上是无限长)的东西篱笆，其方程为y=b，其中b是偶数整数。这两个栅栏在点(a，b)处交叉，并将他的场划分成四个区域。

FJ希望选择a和b，这样四个区域中出现的奶牛就可以合理地“平衡”，没有一个区域包含太多的奶牛。让M是出现在四个区域之一的奶牛的最大数量，FJ想使M尽可能的小。请帮助他确定这个最小的值。

对于前五个测试用例，B保证最多为100。在所有测试用例中，B最多保证为1,000,000。

输入格式(文件balancing.in):

输入的第一行包含两个整数，N和B。接下来的n行分别包含单个cow的位置，指定其x和y坐标。输出格式(文件balancing.out)：您应该输出最小的M值，FJ可以通过最优地定位他的栅栏来达到这个值。

SAMPLE INPUT:

7 10
7 3
5 5
9 7
3 1
7 7
5 3
9 1
SAMPLE OUTPUT:
2

这是我的代码：

    import java.util.*;
    import java.io.*;
    
    public class ACO2016FebP3{

   public static void main(String[] args) throws IOException{
     Scanner in = new Scanner(new File("balancing.in"));
     PrintWriter out = new PrintWriter(new File("balancing.out"));
     
     int N = in.nextInt();
     int B = in.nextInt();
     
     Point[] loc = new Point[N];
     int minX=B, minY=B;
     for(int i=0; i<N; i++){
         int x = in.nextInt();
         int y = in.nextInt();
         loc[i] = new Point(x, y);
         if(x < minX){ minX = x;}
         if(y < minY){ minY = y;}
     }
     
     int result = Integer.MAX_VALUE;
     for(int a = minX+1; a < B-2; a+=2){
         for(int b = minY+1; b < B-2 ; b += 2){
            int[] mArr = new int[4];
            for(Point p : loc){
               if(p.x<a && p.y<b){
                  mArr[0]++;
               }
               if(p.x>a && p.y<b){
                  mArr[1]++;
               }
               if(p.x>a && p.y>b){
                  mArr[2]++;
               }
               if(p.x<a && p.y>b){
                  mArr[3]++;
               }
            }
            int mMax = findMax(mArr);
            result = Math.min(result, mMax);
         }
     }
     out.println(result);
     out.close();
   }
   
   public static int findMax(int[] arr){
      int max = Integer.MIN_VALUE;
      for(int e : arr){
         if(e > max){
            max = e;
         }
      }
      return max;
   }
   
}

class Point{
   int x, y;
   Point(int xx, int yy){
      x = xx;
      y = yy;
   }
}

下面是测试输入数据的方法，这会导致超时错误。

100 5000
4897 217
3507 4953
633 4669
4375 491
4185 1599
1593 3363
931 4501
4823 1585
3621 3631
4077 1373
489 3847
547 4713
4893 773
1011 4881
1965 541
3455 3985
107 4957
37 4977
4927 4961
1453 1335
3133 1267
83 4743
4603 1439
887 4519
2483 741
1429 1169
461 839
255 3801
1261 3951
933 4465
1521 2245
1197 4809
2451 1017
4053 435
4043 1167
3345 433
1079 2539
621 3375
4047 1185
535 2219
417 3387
571 673
3945 1355
849 3473
3775 797
97 4203
4133 1367
4305 1553
4199 521
333 5
485 2633
937 4879
919 1561
3667 567
1527 4463
4659 4387
785 4753
1529 393
401 4623
1043 1433
317 3369
4833 1367
4493 173
2789 957
573 4001
257 1439
3721 983
925 3141
3753 3631
2393 401
649 1681
3669 11
1241 4571
891 2465
3775 1033
4369 3631
1921 209
4553 1529
321 4835
2637 53
837 499
2317 721
3413 1661
1295 4991
687 3729
161 4757
811 4871
471 3189
883 389
4009 635
781 143
1165 2541
2111 69
3425 187
763 2159
3523 1107
1659 4965
1089 1355
3559 1255
133 15

Answer 1

问题解决了。而不是布鲁斯力，我只是检查所有可能的x和y作为a和b。

import java.util.*;
import java.io.*;

public class ACO2016FebP3{
   public static void main(String[] args) throws IOException{
     Scanner in = new Scanner(new File("balancing.in"));
     PrintWriter out = new PrintWriter(new File("balancing.out"));
     
     int N = in.nextInt();
     int B = in.nextInt();
     
     Point[] loc = new Point[N];
     for(int i=0; i<N; i++){
         int x = in.nextInt();
         int y = in.nextInt();
         loc[i] = new Point(x, y);
     }
     
     int result = Integer.MAX_VALUE;

     for(int xIdx = 0; xIdx<N; xIdx++){
         for(int yIdx = 0; yIdx<N; yIdx++){
            int a = loc[xIdx].x-1;
            int b = loc[yIdx].y-1;
            int[] mArr = new int[4];
            for(Point p : loc){
               if(p.x<a && p.y<b){
                  mArr[0]++;
               }
               if(p.x>a && p.y<b){
                  mArr[1]++;
               }
               if(p.x>a && p.y>b){
                  mArr[2]++;
               }
               if(p.x<a && p.y>b){
                  mArr[3]++;
               }
            }
            int mMax = findMax(mArr);
            result = Math.min(result, mMax);
         }
     }
     /*
     int result = Integer.MAX_VALUE;
     for(int a = minX+1; a < B-2; a+=2){
         for(int b = minY+1; b < B-2 ; b += 2){
            int[] mArr = new int[4];
            for(Point p : loc){
               if(p.x<a && p.y<b){
                  mArr[0]++;
               }
               if(p.x>a && p.y<b){
                  mArr[1]++;
               }
               if(p.x>a && p.y>b){
                  mArr[2]++;
               }
               if(p.x<a && p.y>b){
                  mArr[3]++;
               }
            }
            int mMax = findMax(mArr);
            result = Math.min(result, mMax);
         }
     }
     */
     out.println(result);
     out.close();
   }
   
   public static int findMax(int[] arr){
      int max = Integer.MIN_VALUE;
      for(int e : arr){
         if(e > max){
            max = e;
         }
      }
      return max;
   }
   
}

class Point{
   int x, y;
   Point(int xx, int yy){
      x = xx;
      y = yy;
   }
}