CSP-202012-2-期末预测之最佳阈值

【70分思路】

• 本题的难点还是时间复杂度，暴力枚举会导致时间超限。
• 对于每一个可能的阈值theta，代码都重新计算了整个predict数组，统计预测正确的数目，因为有两个嵌套的循环，使得时间复杂度是O(m^2)。

#include <iostream>
using namespace std;
int main() {
    int m;
    cin >> m;
    int* y = new int[m];
    int* result = new int[m];
    int* ac_num = new int[m];

    int ac_num_max = -1, y_max = -1;
    for (int i = 0; i < m; i++)
    {
        cin >> y[i] >> result[i];
        ac_num[i] = 0;
    }

    for (int i = 0; i < m; i++)
    {
        int theta = y[i];
        int* predict = new int[m];

        for (int j = 0; j < m; j++)
        {
            predict[j] = 0;
        }

        // 计算predict
        for (int j = 0; j < m; j++)
        {
            if (y[j] >= theta)
            {
                predict[j] = 1;
            }
        }

        // 统计正确次数
        for (int j = 0; j < m; j++)
        {
            if (predict[j] == result[j])
            {
                ac_num[i]++;
            }
        }

        // 预测正确的次数最多
        if (ac_num[i] > ac_num_max)
        {
            ac_num_max = ac_num[i];
            y_max = theta;
        }
        // 多个阈值均可以达到最高准确率时，选取其中最大的
        else if (ac_num[i] == ac_num_max)
        {
            if (theta > y_max)
            {
                y_max = theta;
            }
        }

        delete[]predict;
    }

    cout << y_max;

    delete[]y;
    delete[]result;
    delete[]ac_num;
    return 0;
}

【100分思路】

【核心思路】：利用排序和一次遍历来减少计算量。思路是先将输入的y数组和结果result数组按照y值排序，然后一次性计算不同theta值对应的正确预测数量。这样做可以将时间复杂度降低到O(m log m)（主要是排序的时间复杂度，之后只需线性时间就可以计算所有可能的theta值）
上述代码通过一种巧妙的方法实现了对不同theta（阈值）的处理，仅通过单次遍历数据即可更新基于不同theta值的预测正确数。这种方法的核心在于利用排序后的数据和对预测正确数的连续更新，而不是重新计算每一个可能的theta值对应的预测正确数。以下是这个过程的详细解释：

具体思路

1. 排序数据： 首先，通过将数据点按y值进行排序，确保在遍历数据时，theta值是逐渐增加的。这意味着，我们只需要考虑在这些y值变化的地方theta可能会导致预测结果的变化，而不是在每个可能的y值。

2. 初始化正确预测数： 在开始遍历之前，计算了一个初始的正确预测数，这是基于假设theta小于最小y值（即所有数据点的预测结果都是1）的情况。这相当于设置了一个非常低的初始阈值，使得所有预测都是1，然后计算这个情况下正确预测的数量。

3. 遍历并更新： 遍历排序后的数据时，每次遇到一个新的y值，都相当于theta发生了变化。

   • 如果theta小于当前的y值，当前点的预测结果会是1；
   • 如果theta等于或大于当前的y值，当前点的预测结果则为0（假设预测规则是y >= theta为1，否则为0）。
   • 每当theta变化，都会影响到当前点的预测正确与否。
     • 如果当前点实际结果为1，那么当theta增加到等于当前点的y值时，之前计入的正确预测数需要减1（因为这个点现在被错误地预测为0）。
     • 如果当前点的实际结果为0，相反的，当theta增加到等于当前点的y值时，之前未计入的正确预测数需要增加1（因为这个点现在被正确地预测为0）。这一逻辑体现在对currentPredictions的更新上。

4. 处理相同的y值： 在实际数据中，可能存在多个数据点具有相同的y值。当处理这样的数据点时，只有在所有具有相同y值的数据点都被考虑完毕后，才会更新theta值。这意味着，如果连续几个数据点有相同的y值，我们会在遍历到最后一个具有该y值的数据点后，才考虑theta值的变化对预测正确数的影响。这一点通过跳过重复y值的逻辑实现，从而确保了每个不同的theta值只被考虑一次。

5. 更新最大准确预测数和theta： 在遍历过程中，每次theta变化后，都会评估当前的正确预测数。如果这个数值超过了之前记录的最大准确预测数，或者在达到相同的最大准确预测数时具有更大的theta值，则更新记录的最大准确预测数和对应的theta值。这保证了在所有考虑的theta值中，选择了能够产生最大准确预测数的最大theta值。

#include <iostream>
#include <algorithm>
using namespace std;

struct Data {
    int y;
    int result;
};

// 比较函数，用于sort对Data数组进行排序，基于y值升序排列
bool compareData(const Data& a, const Data& b) {
    return a.y < b.y;
}

int main() {
    int m;
    cin >> m; 
    Data* data = new Data[m]; 
    for (int i = 0; i < m; i++) {
        cin >> data[i].y >> data[i].result;
    }    
    sort(data, data + m, compareData); // 对数据点按y值进行升序排序

    int correctPredictions = 0; // 正确预测的初始数量，假设所有数据点的预测结果都是1
    for (int i = 0; i < m; i++) {
        if (data[i].result == 1) {
            correctPredictions++; // 统计实际结果为1的数量
        }
    }

    int ac_num_max = correctPredictions; // 记录最大准确预测数
    int y_max = data[0].y; // 记录达到最大准确预测数的y阈值
    int currentPredictions = correctPredictions; // 当前阈值下的准确预测数
    for (int i = 0; i < m; i++) {
        // 如果当前点的实际结果为0，则假设以当前点的y值为阈值时，将使得预测为1的数量增加
        // 因为实际为0但预测为1的情况会减少
        if (data[i].result == 0) {
            currentPredictions++;
        }
        else {
            // 反之，如果实际结果为1，以当前点的y值为阈值会使得这个点预测错误（预测为0），因此准确预测数减少
            currentPredictions--;
        }

        // 跳过重复的y值，避免对相同阈值的重复计算
        if (i < m - 1 && data[i].y == data[i + 1].y) {
            continue;
        }

        // 更新记录的最大准确预测数及对应的y阈值
        // 这里的条件是为了确保，当有多个阈值产生相同的最大准确预测数时，选择y值较大的那个
        if (currentPredictions >= ac_num_max) {
            ac_num_max = currentPredictions;
            // 选择下一个不同的y值作为阈值，确保在所有相同的最大准确预测数中选择最大的y值
            y_max = i < m - 1 ? data[i + 1].y : data[i].y;
        }
    }
    cout << y_max; // 输出达到最大准确预测数的最大y阈值

    delete[] data; // 释放动态分配的内存
    return 0;
}