(C++)202012-2 期末预测之最佳阈值 满分
#include<cstdio>
#include<algorithm>
using namespace std;const int M = 100000;struct Student{int score;int res;//0表示挂科，1表示未挂int times;//表示预测正确的次数 int before;//在它之前的0的个数 int after;//在它之后的1的个数
}stus[M+10];int n,suffix[M+10],prefix[M+10];bool cmp(Student a,Student b){//分数低的排在前面 if(a.score!=b.score){return a.score<b.score;}else{return a.res<b.res;}
}bool cmp2(Student a,Student b){//正确次数多的排在前面，次数一样分高的排在前面 if(a.times!=b.times){return a.times>b.times;}else if(a.score!=b.score){return a.score>b.score;}else{return a.res<b.res;}
}int main(){int i;scanf("%d",&n);//读入 for(i=0;i<n;i++){scanf("%d%d",&stus[i].score,&stus[i].res);} //按分数从低到高排序 sort(stus,stus+n,cmp);//测试点1：看一下排序后的结果
// printf("\n");
// for(i=0;i<n;i++){
// printf("%d,%d\n",stus[i].score,stus[i].res);
// } //计算每个人之前的0的总数 stus[0].before=0; for(i=1;i<n;i++){if(stus[i-1].res==0){stus[i].before=stus[i-1].before+1;}else{stus[i].before=stus[i-1].before;} }//计算每个人之后(含)的1的总数 stus[n].after=stus[n].res;for(i=n-1;i>=0;i--){stus[i].after=stus[i+1].after+stus[i].res;}//计算每个人预测正确的次数 for(i=0;i<n;i++){stus[i].times=stus[i].before+stus[i].after;}//对预测正确的次数进行矫正，即，如果score等于上一个，那么times也等于上一个for(i=1;i<n;i++){if(stus[i].score==stus[i-1].score){stus[i].times=stus[i-1].times;}} //按照预测正确次数从高到低排序 sort(stus,stus+n,cmp2);//测试点2：看一下排序后的结果
// printf("\n");
// for(i=0;i<n;i++){
// printf("%d,%d,before=%d,after=%d\n",stus[i].score,stus[i].times,stus[i].before,stus[i].after);
// } //输出正确次数最高的那个人的分数 printf("%d",stus[0].score); return 0;
}经验：
①本题是典型的利用递推关系来降低时间复杂度
②测试数据当中有一组非常有趣，即
8
5 1
5 0
5 0
2 1
3 0
4 0
100000000 1
1 0
可以看到，同样是阈值5，放在本程序中计算得到预测正确次数是不一样的，最终我加入这段代码解决了这个问题可能导致的错误
//对预测正确的次数进行矫正，即，如果score等于上一个，那么times也等于上一个for(i=1;i<n;i++){if(stus[i].score==stus[i-1].score){stus[i].times=stus[i-1].times;}}
相关文章：
javascript之prototype总结常用方法
//去左右空格String.prototype.trim function(){ return this.replace(/^\s*|\s*$/g,);}//去空格添加至数组集合String.prototype.splitrim function(t){ return this.trim().split(new RegExp(\\s*t\\s*)) }test "testing , splitrim ";var arr test.split…
Power Designer逆向工程导入Oracle表，转为模型加注释
1.打开PowerDesigner ——文件——Reverse Engineer——DataBase 2.选择所要连接数据库版本，此处使用的是oracle version 11g。 3.点击红色区域，选择数据源 4.选择modify 5.在此填写你的数据库名称、连接地址、用户名。确定 6.选择你新建立的连接数据库 …
ubuntu修改主机名后无法解析主机
修改完主机名后在执行sudo命令时，会提示sudo: 无法解析主机。在网上搜了下，找到了解决方法：1.sudo vim /etc/hosts找到如下行：127.0.1.1 XXX修改为：127.0.1.1 （修改后的主机名） 转载于:https://…
(C++)201709-1 打酱油
#include<cstdio> #include<algorithm> using namespace std;//贪心问题，优先级：剩的钱购买5瓶就买5瓶，不够看够不够买三瓶，再不够看够不够买一瓶 int main(){int start,left,num0;//初始的钱，当前剩下的…
【转】实现多行toolTips的类模块
注：本文转自CSDN论坛这里有一个类模块,就是用来实现多行 toolTips 的. Option Explicit Module Name : mdlAPI Written By : Gordon Robinson Date …
POJ 1458
给出两个字符串，求它们最长的公共子字符串长度。 如abfgc acbfefc 最长的公共子字符串为abfc 长度为4 思路：找到s1[i]与s2[j]的时候，相等的话，dp[i1][j1]dp[i][j]1; 不等的话dp[i1][j1]max(dp[i][j1],dp[i1][j]); #include <…
Activity的LaunchMode
在Android中，启动一个Activity有时需要总是创建一个新的对象，有时需要重复使用以后的对象，可以通过在配置activity时通过LaunchMode属性指定。 LaunchMode的属性值： 1、shandard： 标准模式：每次调用startAc…
邻域数、直接密度可达、密度可达、密度相连的概念
例子：如图所示，Eps用一个相应的半径表示，设MinPts3，请分析Q,M,P,S,O,R这5个样本点之间的关系。 易知，P,M,Q,O,SO之间的点,OR之间的点都是核心点 M是从P直接密度可达，Q是从M直接密度可达 Q是从P密度可达(反…
VUE中使用Echarts绘制地图迁移
踩坑说明 很久以前写jsp时使用过echarts的china.js插件，不过echarts是2.0的，目前vue项目中使用echarts3.8.5，直接将china.js插件引入，代码复制，运行一看，GG。地图中央只有一个光溜溜的南海群岛框框…
关于mysql字符集及导入导出
MySQL字符集设置 • 系统变量：– character_set_server：默认的内部操作字符集– character_set_client：客户端来源数据使用的字符集– character_set_connection：连接层字符集– character_set_results：查询结果字符集…
javascrip 常用属性
1 隐藏控件<div style"dispay:none"><asp:TextBox id"txthiddent" run"server"></asp:TextBox></div>2 页面引用带的<script> </script> EnDate.JS<head><!--#Include File"Js/EnDate.js&q…
数据预处理知识点汇总
(一) 数据清理 a) 缺失值填充 i. 忽略元组 ii. 手工填写 iii. 自动填充 使用属性均值推理出最可能的值，如贝叶斯公式或决策树 b) 去除离群点 i. 聚类 ii. LOF iii. 回归函数拟合数据 c) 噪音(包括错误和离群)处理 i. 分箱光滑 d) 纠正不一致数据 (二) …
Android支付接入（五）：机锋网
前边已经陆续跟大家走了一遍运营商和支付宝付费接入，今天跟大家一起看看机锋网的支付接入。事实上付费接入本身并没有太多须要注意的地方，做的多了以后你会发现套路都是大同小异的。而须要注意的地方在于怎么跟游戏兼容及后期的维护，包含增减…
腾讯广告广点通API接入文档(Android)
官方文档地址 如果能够看懂文档的也没有必要再往下面看了。本篇文章就到此结束。 下面记录的是本人在上面锁踩过的坑，因为我发现Mac电脑上面的联系客服不是我想要的。 本来只是内部使用的文档，后来想想还是公开出来，希望能够帮助到人。进入正…
Linux下的下载工具 axel
下载地址：http://wilmer.gaast.net/main.php/axel.html Axel是命令行下的多线程下载工具，支持断点续传，速度通常情况下是Wget的几倍。 下载后使用如下命令编译安装： #tar zxvf axel-1.0a.tar.gz #cd axel-1.0a/ #./con…
集成学习知识点汇总
为啥叫集成学习 结合多个学习器来完成学习任务。 俗话说就是，团结力量大。 个体学习器可以相同可以不同。如果相同叫同质集成，如果不尽相同叫异质集成。 个体学习器最好满足：好而不同。 所谓好(准确性)，就是个体学习器不能太坏&…
hdu 2028 Lowest Common Multiple Plus
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid2028 题目大意：求最小公倍数，用辗转相除法。 1 #include <stdio.h>2 int main ()3 {4 int gcd(int a,int b);5 int a,b,n,i,c;6 while (scanf("%d",&n)…
TreeView
6.遍历TreeView节点(递归算法) private void Page_Load(object sender, System.EventArgs e) { GetAllNodeText(TreeView1.Nodes); } void GetAllNodeText(TreeNodeCollection tnc) { foreach(TreeNode node in tnc) { if(node.Nodes.Count!0) GetAllNodeText(node.Nodes); Res…
FZU 2297 Number theory【线段树/单点更新/思维】
Given a integers x 1, you have to apply Q (Q ≤ 100000) operations: Multiply, Divide. Input First line of the input file contains an integer T(0 < T ≤ 10) that indicates how many cases of inputs are there. The description of each case is given below: …
＜软件过程与改进＞计算大题考点总结与例题
1.PSP_PROBE估算法 常见考法：给历史数据，需要选择代理规模的估算值和程序规模/所需资源的实际值，用以下公式求得拟合公式参数 然后使用公式计算出未知的程序规模/所需资源 例题 2.PSP过程质量的度量指标_yield 常见考法：给出缺…
c语言exit和return区别，在fork和vfork中使用
转自c语言exit和return区别，在fork和vfork中使用 exit函数在头文件stdlib.h中。 简述： exit（0）：正常运行程序并退出程序； exit（1）：非正常运行导致退出程序； r…
WIKI与BLOG殊途同归（转）
现在很多朋友都拥有了自己的BLOG网页，尽管他们可能并不打算走木子美那种写私人日记的路子，但彰显个性、张扬自我的目的，大都类似。其实在这个时候，中国的许多技术迷们已经把目光投向了WIKI。 历经了网络反黄与木子美，中…
Spring MVC中DispatcherServlet理解总结(1)
DispatcherServlet在web.xml中的配置 <context-param><!--默认配置文件为/WEB-INF/[servlet名字]-servlet.xml--><param-name>contextConfigLocation</param-name><param-value>WebApplicationContext的上下文配置</param-value> </con…
功能点度量方法介绍
功能点度量方法是利用软件需求分析度量软件规模。 软件需求分析包括：软件功能需求分析、软件性能需求分析 在需求分析阶段可以利用数据流图和用例图对软件规模进行度量，分别对应功能点度量与用例点度量方法 1.功能点度量方法的分类 第三种 IFPUG是我…
微软2014校园招聘笔试试题
转载请标明出处，原文地址：http://blog.csdn.net/hackbuteer1/article/details/121908071、Which statement(s) is(are) correct about thread and process？Select all that apply.(5 Points) A、Threads share the same address space of the…
vi(vim)快捷键小记
1、前言 vi是“visual interface”的缩写，vim是vi IMproved(增强版的vi)。总结一下自己平时常用的vim快捷键，当是忘记也好，后续会不定期更新。 2、vim 快捷键 快捷键说明vi[m] file打开[新建]文件命令模式可以移动光标、删除字符等h,j,k,l左…
Premiere Pro2.0用DebugMode2.3搭桥小日本4.0输出图解
看图说话，不懂的多试试看首先明确几点：1。3个软件：Premiere Pro2.0、DebugMode（帧服务器）、小日本（TMPGEnc 4.0 XPress）2。渲染过程是在小日本中完成，与DebugMode无关，De…
用例点度量方法介绍
用例点度量方法分为6个步骤，分别是 step 1:计算未调整前的角色(执行者)权重 将角色按照复杂程度分为3类，具体如下 则本例中 UAW1121329 计算未调整前的用例权重UUC 有三种评估用例复杂程度的方法，具体如下 以下是用例权重评估表(普通那…
NYOJ——街区最短路径问题
街区最短路径问题 时间限制：3000 ms | 内存限制：65535 KB难度：4描述一个街区有很多住户，街区的街道只能为东西、南北两种方向。住户只可以沿着街道行走。各个街道之间的间隔相等。用(x,y)来表示住户坐在的街区。例如（…
Git 中常用的 4 个命令
使用 Git 进行版本管理时，肯定不只做提交，有时候也会需要回退修改，并且在回退的基础上进行重新提交，这时候有几个常用的命令就需要用到了，下面分别做介绍。 1、查看提交日志 首先，我们查看当前提交记录的命…