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]期末考试 的相关文章

  • 区间图着色问题

    这是算法导论贪心算法一章的一个习题 题目描述 假定有一组活动 我们需要将它们安排到一些教室 任意活动都可以在任意教室进行 我们希望使用最少的教室完成所有的活动 设计一个高效的贪心算法求每个活动应该在哪个教室进行 这个问题称为区间图着色问题
  • Best Binary String

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

    1 题目源地址 http poj org problem id 2709 2 解题思路 每个颜料盒可能有3 12种颜色 其中每种颜色50ml 任意三种颜色 假设每种颜色Xml 可以混合出Xml的灰色 现在给出所需颜色的种数N 给出N个值分别
  • [NOI 2014复习]斜率优化(BZOJ 1096、BZOJ 1010)

    1 BZOJ 1096 仓库建设 题目链接 http www lydsy com JudgeOnline problem php id 1096 思路 令 f i 1 i f i 1 i 区间 在第i个工厂建立仓库 所需最少总花费 DP方程
  • BZOJ4347 [POI2016]Nim z utrudnieniem

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

    该题连接 这是一道英文题 所以这里就不放原题了 我写一下它的题意 主人要开一个party 而主人有N个派 他要宴请F个人 也就是要有F 1个人要吃派 但这些人又很挑剔 他们每个人吃派只吃一种派 并且还不能容忍其他人吃的派比自己多 所以这就是
  • hdoj 1052 Tian Ji -- The Horse Racing 贪心算法

    这道题就是解决选择策略问题 思路一 先将田忌跟齐王的马的速度数组进行一次冒泡排序 1 如果田忌最慢的马比齐王最慢的马快 则比慢马 2 如果田忌最慢的马比齐王最慢的马慢 则用田最慢的马跟齐最快的马比 消耗齐的快马这是贪心的第一步 3 如果田忌
  • Petya and Exam【Codeforces 1282 C】【贪心】

    Codeforces Round 610 Div 2 C 有N道题目 题目有简单与困难之分 简单的题目花费A分钟 困难的题目花费B分钟 那么考试时间一共有T的情况下 我们是可以提前交卷的 但是有些时间限制 就是譬如说你现在第x分钟交卷 但是
  • 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
  • 【BZOJ 2219】【超详细题解】数论之神

    2219 数论之神 Time Limit 3 Sec Memory Limit 259 MB Submit 365 Solved 33 Submit Status Discuss Description 在ACM DIY群中 有一位叫做 傻
  • 【BZOJ3309】DZY Loves Math(莫比乌斯反演)

    题面 求 i 1a j 1bf gcd a b sum i 1 a sum j 1 bf gcd a b 其中 f x f x 表示 x x分解质因数之后 最高的幂次 题解 完全不会莫比乌斯反演了 先来推式子 d 1a i 1a d j 1
  • 多元Huffman编码问题

    题目链接 题意 最多可以让k堆合并 每一次合并的花费为河合并堆的数量 问最多和最少的花费 题解 最少的花费一定是每次合并的堆数尽可能多 这样我们就会减少前面已经合并的堆的重复计算 所以 每次合并k堆时最少 每次合并2堆时最大 另外 最少的时
  • HDOJ1052

    先用最快马比 不行再用最慢马比 都不行 就送最慢马给忘得最快马 include
  • 2605. 从两个数字数组里生成最小数字

    文章目录 Tag 题目来源 题目解读 解题思路 方法一 枚举比较法 方法二 集合的位运算表示法 写在最后 Tag 贪心 位运算 数组 题目来源 2605 从两个数字数组里生成最小数字 题目解读 给定两个各自只包含数字 1 到 9 的两个数组
  • BZOJ4345 [POI2016]Korale

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

    这道题 是学长给我们布置的学习用的题目 重在给我们讲解了什么是优先队列以及其对应的贪心问题 好了 先送上 中文翻译过的题意 手动 滑稽 Oh those picky N 1 lt N lt 50 000 cows They are so p
  • Educational Codeforces Round 67 (Rated for Div. 2)

    contest链接 A Stickers and Toys time limit per test 2 seconds memory limit per test 256 megabytes input standard input out
  • BZOJ4817 [Sdoi2017]树点涂色(洛谷P3703)

    LCT 线段树 BZOJ题目传送门 洛谷题目传送门 码力不行啊 操作1就是access啦 操作2就是 w x w y 2 w lca x y 1 w x w y 2
  • BZOJ4868 [Shoi2017]期末考试

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

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

随机推荐

  • 【嵌入式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