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

2024-06-19 16:38

本文主要是介绍CCF-CSP认证 202012-2 期末预测之最佳阈值,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

思路写在注释里面了。《算法笔记》P147页,活用递推章节语:“很多题目需要细心考虑过程中是否存在可能的递推关系,如果能找到这样的递推关系,就能使时间复杂度下降不少。例如就一类涉及序列的题目来说,假如序列每一位所需要计算的值都可以通过该位左右两侧的计算结果得到,那么就可以考虑所谓的‘左右两侧的结果’是否能够通过递推进行预处理来得到,这样在后面的使用中就可以不必反复求解。”

PAT B1040/A1093也是这个思路。
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;
struct Student
{int y_{ 0 };int result_{ 0 };
};
bool cmp(const Student &lhs, const Student &rhs)
{if (lhs.y_ != rhs.y_) return lhs.y_ < rhs.y_;return lhs.result_ < rhs.result_;
}
struct ThreeElementArr {int y_{ 0 };int pass_lower_than_y_{ 0 };int fail_higher_than_y_{ 0 };
};
int main()
{
#ifdef LOCALfreopen("input.txt", "r", stdin);
#endifint m; cin >> m; vector<Student> student_set(m);for (int i = 0; i < m; ++i) {cin >> student_set[i].y_ >> student_set[i].result_;}// 根据y,m个人形成一个排序,把m个人划分成rank+1个类(相同的y在相同的类)(rank<m,从0开始)。// 维护一个大小为rank+1的数组,数组元素为三元组,// 三元组的构成为:{这个rank的y,这个rank之前有多少人过了,这个rank之后有多少人没过};// 从前向后扫描一次排好序的student_set获得第二个元,从后向前获得第三个元,时间复杂度O(2N).// 再扫描一遍这个数组,第二个元和第三个元加和结果最小的元素的y就是阈值y.sort(student_set.begin(), student_set.end(), cmp);vector<ThreeElementArr> rank_arr(m);// 第二个元,即小于此分数的人中有多少人没过。int pass_lower_than_y = 0;int rank = 0;for (int i = 0; i < m; ++i) {if (i == 0) {rank_arr[rank].y_ = student_set[i].y_;}else if (i != 0 && student_set[i].y_ != student_set[i - 1].y_) {++rank;rank_arr[rank].y_ = student_set[i].y_;rank_arr[rank].pass_lower_than_y_ = pass_lower_than_y;}if (student_set[i].result_ == 1) {++pass_lower_than_y;}}// 第三个元,也就是分数大于等于此分数的人中有多少人没有过。int rrank = rank;int fail_higher_tan_y = 0;for (int i = m - 1; i >= 0; i--) {if (i != m - 1 && student_set[i].y_ != student_set[i + 1].y_) {--rrank;}if (student_set[i].result_ == 0) {++fail_higher_tan_y;}rank_arr[rrank].fail_higher_than_y_ = fail_higher_tan_y;}// 寻找和最小的元素的yint min=999999999; int min_idx;for (int i = rank; i >= 0; --i) {if (rank_arr[i].fail_higher_than_y_ + rank_arr[i].pass_lower_than_y_ < min) {min = rank_arr[i].fail_higher_than_y_ + rank_arr[i].pass_lower_than_y_;min_idx = i;}}cout << rank_arr[min_idx].y_;
}

这篇关于CCF-CSP认证 202012-2 期末预测之最佳阈值的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1075571

相关文章

Spring WebFlux 与 WebClient 使用指南及最佳实践

《SpringWebFlux与WebClient使用指南及最佳实践》WebClient是SpringWebFlux模块提供的非阻塞、响应式HTTP客户端,基于ProjectReactor实现,... 目录Spring WebFlux 与 WebClient 使用指南1. WebClient 概述2. 核心依

MyBatis-Plus 中 nested() 与 and() 方法详解(最佳实践场景)

《MyBatis-Plus中nested()与and()方法详解(最佳实践场景)》在MyBatis-Plus的条件构造器中,nested()和and()都是用于构建复杂查询条件的关键方法,但... 目录MyBATis-Plus 中nested()与and()方法详解一、核心区别对比二、方法详解1.and()

Spring Boot @RestControllerAdvice全局异常处理最佳实践

《SpringBoot@RestControllerAdvice全局异常处理最佳实践》本文详解SpringBoot中通过@RestControllerAdvice实现全局异常处理,强调代码复用、统... 目录前言一、为什么要使用全局异常处理?二、核心注解解析1. @RestControllerAdvice2

Spring事务传播机制最佳实践

《Spring事务传播机制最佳实践》Spring的事务传播机制为我们提供了优雅的解决方案,本文将带您深入理解这一机制,掌握不同场景下的最佳实践,感兴趣的朋友一起看看吧... 目录1. 什么是事务传播行为2. Spring支持的七种事务传播行为2.1 REQUIRED(默认)2.2 SUPPORTS2

MySQL 中 ROW_NUMBER() 函数最佳实践

《MySQL中ROW_NUMBER()函数最佳实践》MySQL中ROW_NUMBER()函数,作为窗口函数为每行分配唯一连续序号,区别于RANK()和DENSE_RANK(),特别适合分页、去重... 目录mysql 中 ROW_NUMBER() 函数详解一、基础语法二、核心特点三、典型应用场景1. 数据分

深度解析Spring AOP @Aspect 原理、实战与最佳实践教程

《深度解析SpringAOP@Aspect原理、实战与最佳实践教程》文章系统讲解了SpringAOP核心概念、实现方式及原理,涵盖横切关注点分离、代理机制(JDK/CGLIB)、切入点类型、性能... 目录1. @ASPect 核心概念1.1 AOP 编程范式1.2 @Aspect 关键特性2. 完整代码实

MySQL 用户创建与授权最佳实践

《MySQL用户创建与授权最佳实践》在MySQL中,用户管理和权限控制是数据库安全的重要组成部分,下面详细介绍如何在MySQL中创建用户并授予适当的权限,感兴趣的朋友跟随小编一起看看吧... 目录mysql 用户创建与授权详解一、MySQL用户管理基础1. 用户账户组成2. 查看现有用户二、创建用户1. 基

MySQL MCP 服务器安装配置最佳实践

《MySQLMCP服务器安装配置最佳实践》本文介绍MySQLMCP服务器的安装配置方法,本文结合实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下... 目录mysql MCP 服务器安装配置指南简介功能特点安装方法数据库配置使用MCP Inspector进行调试开发指

SQLite3命令行工具最佳实践指南

《SQLite3命令行工具最佳实践指南》SQLite3是轻量级嵌入式数据库,无需服务器支持,具备ACID事务与跨平台特性,适用于小型项目和学习,sqlite3.exe作为命令行工具,支持SQL执行、数... 目录1. SQLite3简介和特点2. sqlite3.exe使用概述2.1 sqlite3.exe

mtu设置多少网速最快? 路由器MTU设置最佳网速的技巧

《mtu设置多少网速最快?路由器MTU设置最佳网速的技巧》mtu设置多少网速最快?想要通过设置路由器mtu获得最佳网速,该怎么设置呢?下面我们就来看看路由器MTU设置最佳网速的技巧... 答:1500 MTU值指的是在网络传输中数据包的最大值,合理的设置MTU 值可以让网络更快!mtu设置可以优化不同的网