CF1132D Streessful Training(二分+贪心+优先队列*2300)

简介: CF1132D Streessful Training(二分+贪心+优先队列*2300)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
typedef long long ll;
using namespace std;
const int N = 3e5 + 10;
ll n, k;
ll a[N], b[N];
struct node {
  ll a;
  ll b;
  ll c;
  bool operator<(const node &w)const {
    return c > w.c;  //从堆底到根 从大到小 即 小根堆
  }
};
bool check(ll x) {
  priority_queue<node>q;
  for (int i = 1; i <= n; i++) {
    if (a[i] / b[i] < k)
      q.push({a[i], b[i], a[i] / b[i]});
  }
  if (q.empty()) return true;
  for (int i = 0; i < k; i++) {
    auto t = q.top();
    q.pop();
    if (t.c < i) return false;
    if ((t.a + x) / t.b  < k) {
      q.push({t.a + x, t.b, (t.a + x) / t.b });
    }
    if (q.empty()) return true;
  }
  return true;
}
int main() {
  scanf("%lld%lld", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
  for (int i = 1; i <= n; i++) scanf("%lld", &b[i]);
  //枚举最小答案
  ll l = 0, r = 3e12 + 10;
  bool f = 0;
  while (l < r) {
    ll mid = l + r >> 1;
    if (check(mid)) {
      r = mid;
      f = 1;
    } else l = mid + 1;
  }
  if (f == 1)
    cout << l << "\n";
  else cout << -1 << "\n";
  return  0;
}
目录
相关文章
Linux中yum、rpm、apt-get、wget的区别,yum、rpm、apt-get常用命令,CentOS、Ubuntu中安装wget
通过本文,我们详细了解了 `yum`、`rpm`、`apt-get`和 `wget`的区别、常用命令以及在CentOS和Ubuntu中安装 `wget`的方法。`yum`和 `apt-get`是高层次的包管理器,分别用于RPM系和Debian系发行版,能够自动解决依赖问题;而 `rpm`是低层次的包管理工具,适合处理单个包;`wget`则是一个功能强大的下载工具,适用于各种下载任务。在实际使用中,根据系统类型和任务需求选择合适的工具,可以大大提高工作效率和系统管理的便利性。
486 25
CVPR 24:ETH Zurich等团队:重新定义小样本3D分割任务,新基准开启广阔提升潜力!
【7月更文挑战第1天】ETH Zurich团队提出了重新定义小样本3D点云分割任务,聚焦于前景泄漏和稀疏点分布问题。他们提出COSeg方法,利用类特定多原型相关性(CMC)和超相关性增强(HCA),以解决现有方法的局限。此外,通过基础原型校准(BPC)改善模型对基础类的敏感性。实验显示COSeg在性能上有显著提升,但其泛化能力和计算需求仍待优化,且遮挡和噪声等挑战仍有待解决。[论文链接](https://arxiv.org/abs/2403.00592)
200 13
HTML5 MathML好用的第三方库推荐
HTML5 的 MathML 对数学公式的展现至关重要,但因浏览器兼容性和复杂性问题,开发者常选用第三方库增强其功能。本文推荐了四个库:MathJax、KaTeX、MathML Cloud 和 jsMath。MathJax 兼容性好,支持多种格式;KaTeX 渲染速度快,适合现代浏览器;MathML Cloud 提供云端转换服务;jsMath 则适用于基本 MathML 支持。根据项目需求选择合适的库,能显著提升数学内容展示质量和用户体验。
【数据结构入门精讲 | 第六篇】队列知识点及考研408、企业面试练习
【数据结构入门精讲 | 第六篇】队列知识点及考研408、企业面试练习
480 0
Baumer工业相机堡盟相机如何使用飞拍功能( 飞拍功能的优点和行业应用)
Baumer工业相机堡盟相机如何使用飞拍功能( 飞拍功能的优点和行业应用)
345 0
排序算法:归并排序(递归和非递归)
排序算法:归并排序(递归和非递归)
334 0
docker overlay2占用大量磁盘空间处理方法
docker overlay2占用大量磁盘空间处理方法
2123 0
解决上传文件时 nginx 413 Request Entity Too Large 错误
一个使用Tomcat 发布的站点,使用Nginx做了代理,在上传文件时发生以下错误: 413 Request Entity Too Large 413 Request Entity Too Large nginx/1.10.3 在使用文件上传组件如:webuploader 上传时只会提示文件上传失败,具体的错误需要打开浏览器的开发者工具才能看到。
3915 0
「Spring Boot 系列」02. Spring Boot的目录结构和启动方式
「Spring Boot 系列」02. Spring Boot的目录结构和启动方式
373 0
「Spring Boot 系列」02. Spring Boot的目录结构和启动方式
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问