CSP CCF： 202104-3 DHCP服务器 （C++）

• 题目来源
• 题目描述
• 解题过程
• 完整代码

链接: CCF DHCP服务器.

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

 map> 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 > &m: y2result) {  
    pair 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 
#include