当前位置: 首页 > article >正文

大顶堆+动态规划+二分

前言:我们这一题需要分类讨论
对于我们左边和右边的我们需要预处理
有点类似反悔堆的做法,得出i之前取出 m 个元素代价最小,并且这个代价一定是递减的(可以推导一下)


题目地址

在这里插入图片描述

#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N = (int)1e5+10;
int v,n,m;
int le[N],rig[N];

struct node
{
    int va,wei;
    bool operator<(node b){
        return va<b.va;
    }
}sto[N];


signed main(){
    cin >> v >> n >> m;
    for(int i=1;i<=n;i++){
        cin >> sto[i].va >> sto[i].wei;
    }
    sort(sto+1,sto+1+n);
    int x = (m&1); m/=2;
    priority_queue<int> q;
    int now = 0;
    for(int i=1;i<=n;i++){
        now += sto[i].wei; q.push(sto[i].wei);
        while(q.size()>m-1+x) now -= q.top(),q.pop();
        le[i] = now;
    }
    now = 0;
    while(q.size()) q.pop();
    for(int i=n;i;i--){
        now += sto[i].wei; q.push(sto[i].wei);
        while(q.size()>m) now -= q.top(),q.pop();
        rig[i] = now;
    }
    int ans = 0;
    if(x){
        for(int i=m+1;i<=(n-m);i++){
            if(le[i-1]+sto[i].wei+rig[i+1]<=v){
                ans = max(ans,sto[i].va);
            }
        }cout << ans;
    }else{
        for(int i=m;i<=(n-m);i++){
            // 左端点取 i
            // 开始二分 右端点
            int l = m , r = (n-m)+2;
            while(l+1<r){
                int mid = (l+r)/2;
                if(le[i-1]+sto[i].wei+rig[mid]<=v) l = mid;
                else r = mid;
            }
            //cout << " i " << i << " " << l << endl;
            if(l>i&&l<=(n-m)+1) ans = max(ans,sto[i].va+sto[l].va);
        }
        cout << ans/2;
    }
    system("pause");
    return 0;
}

http://www.kler.cn/a/305445.html

相关文章:

  • 项目集章程program charter
  • 普通电脑上安装属于自己的Llama 3 大模型和对话客户端
  • ML 系列: 第 23 节 — 离散概率分布 (多项式分布)
  • 类别变量分析——卡方独立性检验卡方拟合优度检验
  • [Docker#8] 容器配置 | Mysql | Redis | C++ | 资源控制 | 命令对比
  • PYNQ 框架 - 中断(INTR)驱动
  • 微信小程序播放音频方法,解决uniapp 微信小程序不能播放本地音频的方法
  • 地震勘探原理视频总结(1-6)
  • K8s 简介以及详细部署步骤
  • python中实用的数组操作技巧i奥,都在这里了
  • 聊点基础的,关于监控,关于告警(prometheus—+grafana+夜莺如何丝滑使用?)
  • Redis的数据类型以及应用场景
  • 4个方法教你图片转PDF怎么弄。
  • redis短信登录模型
  • for循环语句
  • 支持向量机(Support Vector Machines,SVM)—有监督学习方法、非概率模型、判别模型、线性模型、非参数化模型、批量学习、核方法
  • 【STM32 MCU】stm32MCUs 32-bit Arm Cortex-M
  • 关于 openeuler 22.03-LTS-SP4 scp 失败问题的记录
  • c++基础入门二
  • 【RabbitMQ 项目】服务端:数据管理模块之消息队列管理
  • 速盾:高防服务器租用需要注意什么事项
  • FPGA开发:模块 × 实例化
  • postgres_fdw访问存储在外部 PostgreSQL 服务器中的数据
  • 无线麦克风哪款好用,手机领夹麦克风哪个牌子好,麦克风推荐
  • 软件开发详解:同城O2O系统源码的架构设计与外卖跑腿APP的开发要点
  • 在Linux中安装FFmpeg