ccf-csp认证2020-12-2期末预测之最佳阈值: 一种简单解法

• 期末预测之最佳阈值
• • 题目描述
  • 输入输出格式
  • 样例及解释
  • 数据提示
  • 解题思路
  • 代码

期末预测之最佳阈值

自己的第一篇博客。已经大三下期了，之前没有好好学习，现在要准备四月份csp，打算把之前的题目都自己做做。由于课不多，时间比较充裕，可以写好详细注释放上来和大家一起讨论。

题目描述

输入输出格式

样例及解释

数据提示

70% 的测试数据保证 m≤200；
全部的测试数据保证 2≤m≤105。

解题思路

看到测试数据有部分为1e5，两层循环肯定会超时，我一开始也是70分。看了一些别人的代码，一般是把复杂度降为了（nlogn），但有些比较难懂（我太菜了）。观察到可以先对输入的安全指数进行排序，然后对每一个指数，记录比自己小的0的个数，比自己大（或相等）的1的个数，相加作为其对应的预测成功数。这里我们不一个一个遍历，而是在上一个安全指数对应的预测成功数上进行一些小改动，只需要把上一个指数对应的结果反转（比如上一次结果为1算是预测成功，但现在算为失败）,然后比较更新最大的预测成功数，取其对应的安全指数作为最佳阈值。

代码

#include
using namespace std;struct aa{    //随便取的名字 int y;    //安全指数 int re;   //挂科情况（0或1） 
};bool cmp(aa a, aa b){    //按照安全指数从小到大排序 if(a.y!=b.y)return a.y<b.y;
}int main(){int num;cin>>num;    //输入数据组数 aa myaa[num];for(int i=0; i<num; i++){cin>>myaa[i].y>>myaa[i].re;  //输入每个的安全指数和挂科情况 }sort(myaa, myaa+num, cmp);  //按照安全指数从小到大排序  int maxnum = 0;  //当前最大的预测正确次数int sig = 0;  //所求的阈值sigma int nownum = 0;  //当前遍历到的安全指数对应的预测正确次数 for(int i=0; i<num; i++){  //先求出排序后第一个（最小的）安全指数对应的预测正确次数 if(myaa[i].re==1){nownum++;}}maxnum = nownum;for(int i=0; i<num;){   //后面每一个安全指数对应的预测正确次数其实只需要在上一个的基础上进行小小的修改 while(myaa[i].y==myaa[i+1].y){  //如果有连续的安全指数相同 if(myaa[i].re==1)   //如果是1，那么之前是算做预测正确，现在预测错误了，预测正确次数要减一，下同 nownum--;elsenownum++;i++;}if(myaa[i].re==1) //跳出循环后还要再进行一次判断 nownum--;elsenownum++;i++;if(nownum>=maxnum){   //进行比较更新当前最大的预测正确次数，所求阈值就是其对应的安全指数，//由于我们已经排序了，如果有相同的预测正确次数，输出的就是其中最大的安全指数 maxnum = nownum;sig = myaa[i].y;}}cout<<sig;return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！