BZOJ4868 [Shoi2017]期末考试

2023-11-16

YY一下的话感觉代价关于最晚出分时间是一个单峰函数

三分最晚的出分时间

然后贪心一下算代价就行

如果A>B就只用B就行了

要不然的话出分时间小于当前限制的都可以随便往后调直到到达限制,那么先尽量用A,调不到限制以内的再用B即可

#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<cstdio>
#include<map>
#include<bitset>
#include<set>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
#define MAXN 100010
#define MAXM 1010
#define eps 1e-8
#define ll unsigned long long
#define MOD 1000000007
#define INF 1000000000
ll n,m;
ll a[MAXN],b[MAXN];
ll now;
ll A,B,C;
ll ans=1e18;
ll c[MAXN];
ll OK(ll x){
	ll i;
	ll re=0;
	for(i=1;i<=n;i++){
		if(a[i]<x){
			re+=(x-a[i])*C;
		}
	}
	int wzh=1;
	if(A<B){
		ll rem=0;
		for(i=1;i<=m;i++){
			if(b[i]<x){
				rem+=x-b[i];
			}
		}
		for(i=1;i<=m;i++){
			if(b[i]>x){
				ll t=min(rem,b[i]-x);
				re+=A*t;
				re+=B*(b[i]-x-t);
				rem-=t;
			}
		}
	}else{
		for(i=1;i<=m;i++){
			if(b[i]>x){
				re+=(b[i]-x)*B;
			}
		}
	}
	return re;
}
int main(){
	ll stdans;
	ll i;
	scanf("%llu%llu%llu%llu%llu",&A,&B,&C,&n,&m);
	for(i=1;i<=n;i++){
		scanf("%llu",&a[i]);
	}
	for(i=1;i<=m;i++){
		scanf("%llu",&b[i]);
		now=max(now,b[i]);
	}
	ll l=1,r=now;
	//*
	while(r-l+1>=4){
		ll l1=l+(r-l+1)/3;
		ll l2=l+2*(r-l+1)/3;
		ll t1=OK(l1);
		ll t2=OK(l2);
		if(t1<=t2){
			r=l2;
		}else{
			l=l1;
		}
	}
	//*/
	for(i=l;i<=r;i++){
		ans=min(ans,OK(i));
	}
	printf("%llu\n",ans);
	return 0;
}

/*

*/


本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)

BZOJ4868 [Shoi2017]期末考试 的相关文章

  • AcWing 907. 区间覆盖 贪心

    AcWing 907 区间覆盖 给定N个闭区间 ai bi 以及一个线段区间 s t 请你选择尽量少的区间 将指定线段区间完全覆盖 输出最少区间数 如果无法完全覆盖则输出 1 输入格式 第一行包含两个整数s和t 表示给定线段区间的两个端点
  • Best Binary String

    Best Binary String 题意 给一个包含0 1 的字符串 可以换成0或1 要求换完之后使得成本最小 二进制字符串的成本定义为按非降序对字符串进行排序所需的 反转字符串的任意连续子字符串 形式的最小操作数 思路 因为每次操作是反
  • BZOJ4347 [POI2016]Nim z utrudnieniem

    这题 挺厉害 我们可以用f i j k 表示前i个数 选的个数模d余j 异或和为k的方案数 我们要求的是f n 0 s s为所有数的异或和 另外在n是d的倍数的时候要减一 可是这样直接转移的话显然会超时 我们把所有权重从小到大排序 一个数和
  • 【BZOJ】【P1816】【Cqoi2010】【扑克牌】【题解】【水题】

    传送门 http www lydsy com JudgeOnline problem php id 1816 一张图表示我wa了三次的心情 Code include
  • Pie POJ - 3122【贪心、二分】

    该题连接 这是一道英文题 所以这里就不放原题了 我写一下它的题意 主人要开一个party 而主人有N个派 他要宴请F个人 也就是要有F 1个人要吃派 但这些人又很挑剔 他们每个人吃派只吃一种派 并且还不能容忍其他人吃的派比自己多 所以这就是
  • 【二分+贪心】用 N 根绳子裁剪出 M 根等长绳子

    有 N 根绳子 第 i 根绳子的长度为 l i 现在需要 M 根等长的绳子 你可以对这 N 根绳子进行任意裁剪 不能拼接 请你计算出这 M 根绳子最长的长度 输入描述 第一行包括两个整数 N M 含义如题所述 1 lt N M lt 100
  • Polycarp and Div 3【Codeforces Round #496 (Div. 3)【D题】】【贪心】

    应该说是今天凌晨的吧 第一次打Code Forces 懵懵懂懂的 不过感觉还是良好 做了几道签到题 难题还是没有那个水准去做 Polycarp likes numbers that are divisible by 3 He has a h
  • [NOI2010]超级钢琴【RMQ+贪心+堆】

    题目链接 超级棒的一道题 解这道题 需要分一下几步来看 取的是连续段 我们可以对每个可能起点去知道它的最大可能解 起点begin 最大可行解一定是begin L 1 begin R 1中的一个 如果每次都是取最大的话 那么下一个同起点的一定
  • HDOJ 1052 Tian Ji -- The Horse Racing

    Tian Ji The Horse Racing Time Limit 2000 1000 MS Java Others Memory Limit 65536 32768 K Java Others Total Submission s 2
  • River Jumping【贪心+模拟】

    题目链接 我们可以贪心的从前往后 每次选最接近的且满足条件的这样的贪心 然后从后往前的时候 就是直接用倒着一个个判断是否合法即可 include
  • AcWing 104. 货仓选址

    题目 在一条数轴上有 N 家商店 它们的坐标分别为 A1 AN 现在需要在数轴上建立一家货仓 每天清晨 从货仓到每家商店都要运送一车商品 为了提高效率 求把货仓建在何处 可以使得货仓到每家商店的距离之和最小 输入格式 第一行输入整数N 第二
  • NYOJ 586 疯牛 & POJ 2456(二分搜索 + 贪心)

    疯牛 时间限制 1000 ms 内存限制 65535 KB 难度 4 描述 农夫 John 建造了一座很长的畜栏 它包括N 2 lt N lt 100 000 个隔间 这些小隔间依次编号为x1 xN 0 lt xi lt 1 000 000
  • Voting【Codeforces 1251 E1 && E2】【贪心】

    Educational Codeforces Round 75 Rated for Div 2 E2 Now elections are held in Berland and you want to win them More preci
  • BZOJ4345 [POI2016]Korale

    在病房里日题真是一种独特的体验 首先考虑求第一问 我们先把所有元素排序 我们用优先队列维护选数的集合 对每个集合维护集合里的元素的和v和最后一个元素 即最大的元素 lst 初始的时候我们把只包含最小元素的集合推入队列 那么我们取出一个队头元
  • Stall Reservations POJ - 3190

    这道题 是学长给我们布置的学习用的题目 重在给我们讲解了什么是优先队列以及其对应的贪心问题 好了 先送上 中文翻译过的题意 手动 滑稽 Oh those picky N 1 lt N lt 50 000 cows They are so p
  • 贪心——字典序最小问题

    https vjudge net problem POJ 3617 题目简单理解就是 给定长度为N的字符串为S 要构造一个长度为N的字符串T 起初 T 是一个空串 随后反复进行下列任意操作 从S的头部删除一个字符串 加到T的尾部 从S的尾部
  • 货仓选址(贪心)

    我之前在多篇博客中提到货仓选址 却发现从未仔细介绍过货舱选址 今天就来好好说一下货舱选址这个问题 就以这个图来说 我们假设Ap 1 gt x gt Ap 那么距离之和也就是 x A1 x A2 x Ap A p 1 x A p 2 x An
  • BZOJ3425 Poi2013 Polarization

    最小值一定是n 1 每条边贡献一个答案 显然 首先我们要证明这道题的一个性质 最优解一定具有如下形式 以树的某一个重心 可以是任意一个 为根 根的每一个子树里的所有边要么都指向根 要么都指向叶子 引理 首先对于一棵树 我们把所有边的朝向反转
  • 编程之美2015初赛第二场AB

    题目1 扑克牌 时间限制 2000ms 单点时限 1000ms 内存限制 256MB 描述 一副不含王的扑克牌由52张牌组成 由红桃 黑桃 梅花 方块4组牌组成 每组13张不同的面值 现在给定52张牌中的若干张 请计算将它们排成一列 相邻的
  • Match Points【Codeforces 1156C】【二分答案】

    题目链接 题意有点像上海EC某年的一道铜牌题 具体是哪年记不得了 我们要去N个的关系 使得最多的匹配对达到他们的差值 Z 这样的情况 有这样的一组数据可以很好的反映这道题为什么有人会WA了 4 3 1 4 5 7 但是 同时也证明了 我们取

随机推荐

  • 【嵌入式Linux】开发环境搭建

    一 概述 在进行某一个芯片平台开发前 一般都需要在电脑上安装一系列软件 然后在这些软件上阅读 编写 编译和调试在该平台上运行的代码 最后将编写好的代码通过某种方式烧录到该芯片的对应地址运行 在电脑上安装的这一系列软件的过程 就是开发环境的搭
  • Python数据类型——字符串、列表、元组

    文章目录 一 字符串 二 列表 三 元组 四 字符串 列表和元组的常用方法 一 字符串 在Python中 可以使用单引号或者双引号来创建字符串 单引号或者双引号没有任何区别 字符串也可以赋值给变量 字符串 str1 字符串 str2 字符串
  • Android Studio使用常见问题(一)

    一 无法成功build 1 出现如下错误 Error Unable to tunnel through proxy Proxy returns HTTP 1 1 400 Bad Request 2 原因分析 本地gradle版本与项目制定的
  • php代码学习(二)绕过空白过滤

    绕过空白过滤
  • 华为OD社招面试(技术二面完)--总结复盘

    2020年4月22日 华为OD社招面试复盘总结 一 华为OD简介 首先来解释一下什么是华为OD面试 OD一般是指的是华为的 外包 公司 比如像德科这种 网上其实有很多人都吐槽过这个招聘模式 因为招进去的人不直接是华为内部的人 挂在德科名下或
  • windows批处理:if else的踩坑点及排版优化

    参考 https www jianshu com p f0bde7d355a4 总结 见参考文章
  • python提取excel一列或多列数据另存为新表(1)

    系列文章目录 文章目录 系列文章目录 前言 一 python提取excel指定一列保存到新表 二 python提取excel指定两列保存到新表 总结 前言 一 python提取excel指定一列保存到新表 原数据举例如下 提取B列另存到新表
  • DFS深度优先搜索

    目录 一 DFS的概念 DFS的定义 DFS的搜索方式 DFS采用的数据结构 DFS的特点 二 DFS的实战应用 1 排列数字 2 n 皇后问题 一 DFS的概念 DFS的定义 DFS Depth First Search 深度优先搜索 是
  • 阈值分割法

    阈值分割法可以说是图像分割中的经典方法 它利用图像中要提取的目标与背景在灰度上的差异 通过设置阈值来把像素级分成若干类 从而实现目标与背景的分离 一般流程 通过判断图像中每一个像素点的特征属性是否满足阈值的要求 来确定图像中的该像素点是属于
  • chatGPT插件是什么,chatGPT插件作用介绍

    简介 openAI团队已经在 ChatGPT 中实现了对插件的初步支持 插件是专门为以安全为核心原则的语言模型设计的工具 可帮助 ChatGPT 访问最新信息 运行计算或使用第三方服务 目前体验与开发需要先加入等候名单 官网介绍链接 htt
  • java中如何导入同一个包下其他类文件中的方法,举个例子

    在 Java 中 可以使用 import 关键字导入同一个包下的其他类文件中的方法 例如 假设在同一个包 com example 下有两个类 ClassA 和 ClassB 那么可以在 ClassB 中导入 ClassA 中的方法 代码如下
  • LeetCode:二叉树的遍历方式(13道经典题目)

    LeetCode 二叉树的遍历方式 13道经典题目 本文带来与二叉树的遍历方法有关的经典题目 主要实现是C 144 二叉树的前序遍历 94 二叉树的中序遍历 145 二叉树的后序遍历 102 二叉树的层序遍历 107 二叉树的层序遍历 II
  • 盒模型BFC渲染机制

    目录 一 BFC基本慨念 二 BFC渲染规则 三 如何创建BFC元素 一 BFC基本慨念 一个块格式化上下文 block formatting context 是Web页面的可视化CSS渲染出的一部分 它是块级盒布局出现的区域 也是浮动层元
  • Python爬虫(JS逆向) 抓取POCO图片/Json数据处理/保存本地详细案例

    文章目录 目录 文章目录 前言 一 分析页面 二 逆向过程 2 1 分析参数 2 2 sign code值 2 3 扣代码 三 请求数据 处理Json数据以及把图片保存到本地 3 1 引入库 3 2 生成时间戳和参数 3 3 发起请求 四
  • SVN使用步骤

    1 基本操作 2 提交之间看一下变更内容 3 显示日志 是查看所有提交的记录 4 撤销和恢复操作 撤销本地修改 或者点击提交的时候 还原 把修改的撤销掉 第二种情况 内容已经提交上去了 点击提交日志 进行操作 只是撤销了本地 接着还需要继续
  • JS姓名和手机号脱敏处理

    export const mixins 身份证脱敏 methods 身份证号脱敏 setCertNo certNo if certNo certNo length gt 10 var certNo certNo trim let cert1
  • 单片机学习,设置一个密码锁

    用矩形键盘和LCD1602设置一个单片机 这是做完后所有所需要的文件 模板 具体模板以及功能参考我之前发的文章 51单片机常用的一些模块 模块化编程 延时函数模块 delay 独立按键模块 key 数码管模块 Nixie LCD1602模块
  • 【论文精读】IGEV-MVS:Iterative Geometry Encoding Volume for Stereo Matching

    今天读的是发表于CVPR2023的文章 作者全部来自于华中科技大学 文章链接 Iterative Geometry Encoding Volume for Stereo Matching 项目地址 GitHub 目录 Abstract 1
  • C语言中的条件操作符和前置++、后置++的区别

    一 条件操作符 条件运算符 conditional operator 有时候也称为三元运算符 ternary operator 或者trinary operator 因为它是唯一需要 3 个操作数的运算符 exp1 exp2 exp3 条件
  • BZOJ4868 [Shoi2017]期末考试

    YY一下的话感觉代价关于最晚出分时间是一个单峰函数 三分最晚的出分时间 然后贪心一下算代价就行 如果A gt B就只用B就行了 要不然的话出分时间小于当前限制的都可以随便往后调直到到达限制 那么先尽量用A 调不到限制以内的再用B即可 inc