CSP CCF： 202012-2 期末预测之最佳阈值 （C++）

题目来源

链接: CCF 期末预测之最佳阈值.

题目描述

解题过程

1. 题目要求为选取合适的安全指数阈值 Θ \Theta Θ ， 使得该阈值对这 m 位同学上学期的挂科情况进行预测，预测正确的次数最多。
2. 输入 m 位同学的安全指数 y i y_i yi​ 和 r e s u l t i result_i resulti​时，使用 map<int, pair<int, int> > y2result (意味着 {安全指数， <未通过人数, 通过人数> }， {…}, …)来存储不同安全指数的未通过和通过的人数。 此外，使用passNum、npassNum 分别记录 总的通过人数，总的未通过人数。

 map<int, pair<int, int>> y2result;
 int passNum = 0, npassNum = 0;  // 总的通过人数， 总的未通过人数
 for (int i = 1; i <= m; ++i) {
   int yi, resulti;
     cin>>yi>>resulti;

     if (y2result.count(yi) == 0) {  // 未记录过该安全指数时， 初始化一下
         y2result[yi].first = 0;
         y2result[yi].second = 0;
     }
     if (resulti == 1) {  // pass
         y2result[yi].second += 1;
         ++passNum;
     }
     else {              // not pass
         y2result[yi].first += 1;
         ++npassNum;
     }
 }

3. 对于 Θ i \Theta_i Θi​ == y i y_i yi​时， 假设有 curPassNum 个安全指数低于 y i y_i yi​的同学通过考试， curNPassNum 个安全指数低于 y i y_i yi​ 的同学未通过了考试。那么当前预测正确的人数curAcc = curNPassNum + passNum - curPassNum。

   因为C++ 的 map底层实现是按字典序来排序各元素的，所以下面在遍历 y i y_i yi​ (即 Θ i \Theta_i Θi​)时，是从小到大遍历安全指数的。

int curPassNum = 0, curNPassNum = 0;
int bestTheta, int bestAccuracy = 0;
for (pair<const int, pair<int, int> > &m: y2result) {  
    pair<int, int> cur = m.second;

    int curAcc = curNPassNum + passNum - curPassNum ;
    if (curAcc >= bestAccuracy) {
        bestTheta = m.first;
        bestAccuracy = curAcc;
    }

    curNPassNum += cur.first;  // not pass
    curPassNum += cur.second;
}

完整代码

#include <iostream>
#include <map>

using namespace std;

int main() {
    int m;
    cin>>m;

    map<int, pair<int, int>> y2result;
    int passNum = 0, npassNum = 0;
    for (int i = 1; i <= m; ++i) {
        int yi, resulti;
        cin>>yi>>resulti;

        if (y2result.count(yi) == 0) {  // 未记录过该安全指数时， 初始化一下
            y2result[yi].first = 0;
            y2result[yi].second = 0;
        }
        if (resulti == 1) {  // pass
            y2result[yi].second += 1;
            ++passNum;
        }
        else {              // not pass
            y2result[yi].first += 1;
            ++npassNum;
        }
    }

    int curPassNum = 0, curNPassNum = 0;
    int bestTheta, int bestAccuracy = 0;
    for (pair<const int, pair<int, int> > &m: y2result) {
        pair<int, int> cur = m.second;

        int curAcc = curNPassNum + passNum - curPassNum ;
        if (curAcc >= bestAccuracy) {
            bestTheta = m.first;
            bestAccuracy = curAcc;
        }

        curNPassNum += cur.first;  // not pass
        curPassNum += cur.second;
    }

    cout<<bestTheta<<endl;

    return 0;
}