USACO 2016 Feb Bronze

Question

我搞不懂这USACO 2016 Bronze的暴力搜索了，我过了六个点超时4个点，我暴搜的方法有点问题感觉

#include <bits/stdc++.h>
using namespace std;
int N, B, minv = 1000000;
struct aa {
    int xp;
    int yp;
};

bool cmp (aa x, aa y) { // 排序函数 
    if (x.xp == y.xp) return y.yp > x.yp;
    return x.xp < y.xp;
} 

int main () {
    freopen("balancing.in", "r", stdin);
    freopen("balancing.out", "w", stdout);
    cin >> N >> B;
    aa coordinate[110];
    int minv_y = 1000000, maxv_y = -1; // 找到y轴十字的起始位置和终止位置 
    for (int i = 1; i <= N; i++) {
        cin >> coordinate[i].xp >> coordinate[i].yp;
        minv_y = min (minv_y, coordinate[i].yp);
        maxv_y = max (maxv_y, coordinate[i].yp);
    }
    sort (coordinate + 1, coordinate + N + 1, cmp);
    
    for (int i = coordinate[1].xp - 1; i <= coordinate[N].xp + 1; i += 2) { // 竖直渐近线 
        for (int j = minv_y - 1; j <= maxv_y + 1; j += 2) { // 水平渐近线 
            int zone1 = 0, zone2 = 0, zone3 = 0, zone4 = 0, maxv = -1;
            for (int x = 1; x <= N; x++) {
                if (coordinate[x].xp > i && coordinate[x].yp > j) zone1++;
                else if (coordinate[x].xp > i && coordinate[x].yp < j) zone4++;
                else if (coordinate[x].xp < i && coordinate[x].yp > j) zone2++;
                else if (coordinate[x].xp < i && coordinate[x].yp < j) zone3++;
            } 
            maxv = max (maxv, zone1);
            maxv = max (maxv, zone2);
            maxv = max (maxv, zone3);
            maxv = max (maxv, zone4);
            minv = min (minv, maxv);
        }
    }
    cout << minv;
    
    fclose (stdin);
    fclose (stdout);
    
    return 0;
} 

我还没有学二分离散这些高级的东西，从优化暴力搜索的角度怎么解？
能讲的详细点吗，我听懂了成功提交就立马结题

Answer 1

你的代码实现了一个暴力搜索的方法，但是在每个点的遍历中，你使用了四个循环嵌套，导致时间复杂度较高。为了优化这个暴力搜索，我们可以尝试减少循环嵌套的层数，以及减少每个点的遍历次数。

这里有一些建议：

1. 合并坐标点信息： 你可以将坐标点的信息合并成一个结构体或者pair，这样可以更方便地处理和传递坐标信息，减少数组的使用。

struct Point {
    int x, y;
};

vector<Point> coordinates;

1. 不必每次都排序： 由于你在每次搜索之前都对坐标进行排序，这是一个开销很大的操作。可以考虑在读入坐标的时候就按照需要的顺序进行排序。

sort(coordinates.begin(), coordinates.end(), cmp);

1. 用一个数组记录每个区域的个数： 不必每次都循环遍历所有点来计算每个区域的个数，可以在一次遍历中记录下每个区域的个数。

int zoneCount[4] = {0}; // 分别记录四个区域的个数
for (int x = 0; x < N; x++) {
    if (coordinates[x].x > i && coordinates[x].y > j) zoneCount[0]++;
    else if (coordinates[x].x > i && coordinates[x].y < j) zoneCount[3]++;
    else if (coordinates[x].x < i && coordinates[x].y > j) zoneCount[1]++;
    else if (coordinates[x].x < i && coordinates[x].y < j) zoneCount[2]++;
}

1. 在遍历过程中更新最小值： 在每次遍历的过程中就更新最小值，而不是等到所有遍历结束再更新。

minv = min(minv, max(zoneCount[0], max(zoneCount[1], max(zoneCount[2], zoneCount[3]))));

1. 遍历时跳过相同的x坐标： 在竖直渐近线的循环中，可以跳过相同的x坐标，因为它们对结果不会有影响。

for (int x = 0; x < N; x++) {
    if (x > 0 && coordinates[x].x == coordinates[x - 1].x) continue;
    // 其他处理
}

通过这些优化，你的代码在时间复杂度上应该能有一些改善。希望这些建议能帮助你更好地理解和改进你的暴力搜索实现。