202012-2 期末预测之最佳阈值

简介: 202012-2 期末预测之最佳阈值

本题链接 期末预测之最佳阈值

本博客给出本题截图

4.png

C++

#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n;
PII q[N];
int s[2][N];
int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i ++ ) scanf("%d%d", &q[i].x, &q[i].y);
    sort(q + 1, q + n + 1);
    for (int i = 0; i < 2; i ++ )
        for (int j = 1; j <= n; j ++ )
            s[i][j] = s[i][j - 1] + (q[j].y == i);
    int cnt = -1, res;
    for (int i = 1; i <= n; i ++ )
    {
        int t = s[0][i - 1] + s[1][n] - s[1][i - 1];
        if (t >= cnt) cnt = t, res = q[i].x;
        while (i + 1 <= n && q[i + 1].x == q[i].x) i ++ ;
    }
    printf("%d\n", res);
    return 0;
}

总结

得70分的原因:没有使用前缀和处理

注意数据范围是 1e5 级别的,O(n ²) 时间复杂度显然是不行的,需要 O(nlogn)

题干较长,注意题目中的细节处理

前缀和的基础运用

前缀和

目录
相关文章
|
安全 Java PHP
PHP/JAVA交易所系统开发(成熟案例)丨需求步骤丨指南详细丨方案逻辑丨逻辑教程丨源码功能
An exchange refers to an institution or platform that provides a centralized market for buying and selling transactions, where participants can trade various assets, such as securities, commodities, cryptocurrencies, etc. Exchanges provide market infrastructure and rules to facilitate compliant, saf
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
653 68
|
数据库 数据库管理
【异常解决】svn报“Previous operation has not finished; run ‘cleanup‘ if it was interrupted”的错误解决方案
【异常解决】svn报“Previous operation has not finished; run ‘cleanup‘ if it was interrupted”的错误解决方案
2033 0
|
存储 缓存 网络协议
【专栏】理解并优化DNS设置对于提高网络速度至关重要
【4月更文挑战第28天】本文探讨了DNS服务器是否能加快网络访问速度。DNS负责将域名转换为IP地址,其查询时间、缓存机制和地理位置都影响网络速度。优化DNS配置,如选择快速的公共DNS服务、使用附近的服务器、确保设备正确配置和利用DNS缓存,都能有效提升网络体验。理解并优化DNS设置对于提高网络速度至关重要。
2811 2
|
Java C++ Docker
Docker再学习 - 阿里加速配置篇
Docker再学习 - 阿里加速配置篇
1651 0
|
机器学习/深度学习 算法 云计算
文字改视频技术:Rerender A Video
Rerender A Video 的实现技术结合了深度学习、计算机视觉、图像处理、GPU 加速和云计算等多种先进技术,旨在提供高效、优质的视频渲染和增强功能。
314 2
|
Kubernetes Cloud Native Linux
云原生入门:Kubernetes的简易部署与应用
【8月更文挑战第31天】在云原生的世界里,Kubernetes(K8s)是一颗璀璨的星。本文将带你走进K8s的世界,从安装到简单应用,轻松驾驭这个强大的容器编排工具。让我们一起探索云原生的奥秘,解锁新技能!
|
小程序
微信小程序下载代码
微信小程序下载代码
|
JavaScript 前端开发 Serverless
JavaScript 基础(4) - 笔记
JavaScript 是 Web 的编程语言。 所有现代的 HTML 页面都可以使用 JavaScript。 学习从初级到高级 JavaScript 知识。
293 1
|
弹性计算 数据安全/隐私保护 CDN
[新手指南参考]阿里云服务器ecs实例选择(地域+CPU+操作系统+带宽)
简介: 应该如何选择阿里云服务器呢?购买什么配置的阿里云服务器是适合自己的呢?下面我们就来说说如何选择阿里云服务器配置。
[新手指南参考]阿里云服务器ecs实例选择(地域+CPU+操作系统+带宽)