寒假思维训练day20

更新一道1600的反向贪心


题意:

有n场比赛,且小明的智商是m,每场比赛需要的智商是a[i],当m >= a[i]时, 可以直接看题,当a[i] > m时,需要智商m减1才能看这道题,当智商为0不能继续往下看题,问最多能看多少题


题解:

1、已知n, m, a[1],..., a[n]

2、

m >= n时,我们直接可以全部都看,答案为n。

m < n时,假设最优解为:\{a[i_1], a[i_2], a[i_3], ..., a[i_k]\}, 我们来构造出一个等价的解,我们此时来看最后一次选择, 当看i_k != n时,必然要有m >= 1, 那么此时因为最优解当中不存在n, 显然m恰好为1, 那我们不妨不选i_k,选择n,此时我们的解可以构造成\{a[i_1], a[i_2], a[i_3], ..., a[n]\}, 在此基础上我们进行贪心,往前贪心,因为到a[n]时我们的智商 >= 1,那我们从后往前倒推,定初始值sum = 0, 当sum >= a[i], 我们取走i, 只要sum < m, 我们取走当前位,sum += 1,因为当尽可能多的取走可以使得sum 尽可能更早地逼近m, 对前面的选择更有利 。


代码 (cpp):

#include <bits/stdc++.h>
#define int long long 
#define lowbit(x) (x&-x)
using namespace std; 
const int N = 2e5 + 10; 
const int inf = 0x3f3f3f3f; 
int n, m;  
int a[N]; 
int cn[N]; 
void solve() {cin >> n >> m; for(int i = 1; i <= n; i ++ ) cin >> a[i]; vector<int> ans(n + 1, 0); int t = 0; for(int i = n; i >= 1; i -- ) {if(t >= a[i]) ans[i] = 1; else if(t < m) t ++, ans[i] = 1; }for(int i = 1; i <= n; i ++ ) cout << ans[i]; cout << endl; }
signed main() {int ts; cin >> ts; while(ts -- ) solve(); return 0; 
}
/* 1
5 4
5 1 5 1 4 3 */ 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2780144.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

UR10+gazebo+moveit吸盘抓取搬运demo

使用ur10gazebo开发了一个简易吸盘抓取箱子码垛的仿真过程&#xff0c;机械臂控制使用的是moveit配置。 本博客对部分关键的代码进行解释。 代码运行环境&#xff1a;支持ubuntu16、 18、 20&#xff0c; ros版本是ros1&#xff08;经过测试&#xff09;。 1、搬运场景 场景的…

视频讲解:优化柱状图

你好&#xff0c;我是郭震 AI数据可视化 第三集&#xff1a;美化柱状图&#xff0c;完整视频如下所示&#xff1a; 美化后效果前后对比&#xff0c;前&#xff1a; 后&#xff1a; 附完整案例源码&#xff1a; util.py文件 import platformdef get_os():os_name platform.syst…

Matlab图像处理——图像边缘检测方法(算子)

1.edge函数语法 BW edge(I) BW edge(I,method) BW edge(I,method,threshold) BW edge(I,method,threshold,direction) BW edge(___,"nothinning") BW edge(I,method,threshold,sigma) BW edge(I,method,threshold,h) BW edge(I) 返回二值图像 BW&#xff0…

如何编写高效的可复用程序

子程序、FB 、FC等的相关内容还可以查看下面文章链接&#xff1a; https://rxxw-control.blog.csdn.net/article/details/124524693https://rxxw-control.blog.csdn.net/article/details/124524693 1、FB和FC编程的优点 待续.....

第4集《佛说四十二章经》

请大家打开讲议第四面&#xff0c;第一章&#xff0c;出家证果。 佛言&#xff1a;辞亲出家&#xff0c;识心达本&#xff0c;解无为法&#xff0c;名曰沙门。 在经文的刚开始啊&#xff0c;佛陀把修道的沙门提出了两个基本的条件&#xff1a; 第一个是辞亲出家&#xff0c;…

C#,卢卡斯数(Lucas Number)的算法与源代码

1 卢卡斯数&#xff08;Lucas Number&#xff09; 卢卡斯数&#xff08;Lucas Number&#xff09;是一个以数学家爱德华卢卡斯&#xff08;Edward Lucas&#xff09;命名的整数序列。爱德华卢卡斯既研究了这个数列&#xff0c;也研究了有密切关系的斐波那契数&#xff08;两个…

Canvas笔记05:像素操作,可以对图像进行像素级别控制和处理

hello&#xff0c;我是贝格前端工场&#xff0c;最近在学习canvas&#xff0c;分享一些canvas的一些知识点笔记&#xff0c;本期分享canvas像素操作的知识&#xff0c;欢迎老铁们一同学习&#xff0c;欢迎关注&#xff0c;如有前端项目需要协助可私聊。 一、什么是像素操作 Ca…

C++提高编程(黑马笔记)

C提高编程 模版 特点&#xff1a; 只是一个框架&#xff0c;不可以直接使用通用并不是万能的 泛型主要利用模版 函数模版 语法&#xff1a; template<typename T> 函数# include<iostream> using namespace std;template<typename T> void MySwap(T&a…

分享66个时间日期JS特效,总有一款适合您

分享66个时间日期JS特效&#xff0c;总有一款适合您 66个时间日期JS特效下载链接&#xff1a;https://pan.baidu.com/s/1niQUpDSs10gfGYKYnEgKRg?pwd8888 提取码&#xff1a;8888 Python采集代码下载链接&#xff1a;采集代码.zip - 蓝奏云 学习知识费力气&#xff0c;…

Solidworks:平面草图练习

继续练习平面草图&#xff0c;感觉基本入门了。

ChatGPT偷懒、变慢的罪魁祸首竟然是它?!系统提示词塞满垃圾!

大家好&#xff0c;我是木易&#xff0c;一个持续关注AI领域的互联网技术产品经理&#xff0c;国内Top2本科&#xff0c;美国Top10 CS研究生&#xff0c;MBA。我坚信AI是普通人变强的“外挂”&#xff0c;所以创建了“AI信息Gap”这个公众号&#xff0c;专注于分享AI全维度知识…

gtkmm4 应用程序使用 CSS 样式

文章目录 前言css选择器css文件示例源代码效果动态设置css-classes 前言 程序样式和代码逻辑分离开 使代码逻辑更可观 css选择器 Cambalache提供了两种css-classes 相当于css里的类名:class“类名”css-name 相当于css里的标签名:spin div p 啥的 如上我设置了这个按钮控件的…

前端JavaScript篇之异步编程的实现方式?

目录 异步编程的实现方式&#xff1f;1. 回调函数2. Promise3. Async/Await4. Generator 异步编程的实现方式&#xff1f; 异步编程是处理需要等待的操作的一种方式&#xff0c;比如读取文件、发送网络请求或处理大量数据。在JavaScript中&#xff0c;有几种常见的实现方式&am…

15 ABC基于状态机的按键消抖原理与状态转移图

1. 基于状态机的按键消抖 1.1 什么是按键&#xff1f; 从按键结构图10-1可知&#xff0c;按键按下时&#xff0c;接点&#xff08;端子&#xff09;与导线接通&#xff0c;松开时&#xff0c;由于弹簧的反作用力&#xff0c;接点&#xff08;端子&#xff09;与导线断开。 从…

一键打造属于自己漏扫系统

0x01 工具介绍 本系统是对Web中间件和Web框架进行自动化渗透的一个系统,根据扫描选项去自动化收集资产,然后进行POC扫描,POC扫描时会根据指纹选择POC插件去扫描,POC插件扫描用异步方式扫描.前端采用vue技术,后端采用python fastapi。 0x02 安装与使用 1、Docker部署环境 编译…

MongoDB 与 mongo-express docker 安装

MongoDB 和 mongo-express 与 MySQL 不同&#xff0c;MongoDB 为 NoSQL 数据库&#xff0c;MongoDB 中没有 table &#xff0c;schema 概念&#xff0c;取而代之的 collection&#xff0c;其中 collection 存储的为 BSON 格式&#xff0c;是一种类似于 JSON 的用于存储 k-v 键…

案例:CentOS8 在 MySQL8.0 实现半同步复制

异步复制 MySQL 默认的复制即是异步的&#xff0c;主库在执行完客户端提交的事务后会立即将结果返给给客户端&#xff0c;并不关心从库是否已经接收并处理&#xff0c;这样就会有一个问题&#xff0c;主节点如果 crash 掉了&#xff0c;此时主节点上已经提交的事务可能并没有传…

Blazor SSR/WASM IDS/OIDC 单点登录授权实例3-服务端管理组件

目录: OpenID 与 OAuth2 基础知识Blazor wasm Google 登录Blazor wasm Gitee 码云登录Blazor SSR/WASM IDS/OIDC 单点登录授权实例1-建立和配置IDS身份验证服务Blazor SSR/WASM IDS/OIDC 单点登录授权实例2-登录信息组件wasmBlazor SSR/WASM IDS/OIDC 单点登录授权实例3-服务端…

Vue源码系列讲解——模板编译篇【二】(模板解析阶段)

目录 1. 整体流程 2. 回到源码 3. 总结 1. 整体流程 上篇文章中我们说了&#xff0c;在模板解析阶段主要做的工作是把用户在<template></template>标签内写的模板使用正则等方式解析成抽象语法树&#xff08;AST&#xff09;。而这一阶段在源码中对应解析器&…

使用Cargo创建、编译与运行Rust项目

在 Rust 开发中&#xff0c;Cargo 是一个非常重要的工具&#xff0c;它负责项目的构建、管理和依赖管理。以下是如何使用 Cargo 创建、编译和运行 Rust 项目的详细步骤。 1. 创建新项目 首先确保你已经在计算机上安装了 Rust 和 Cargo。然后&#xff0c;在命令行中输入以下命…