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

[优先队列] P3611 [USACO17JAN] Cow Dance Show S 题解

神人题。

首先要二分一下\(k\)。然后呢?然后就不会了。

查看题解仔细思考后,发现模拟就行了。

开一个堆,把前 \(k\) 个牛放进去。

然后对于后面的牛,你每次把堆顶的牛拿出来,然后把后面的牛放进去。由于要等到堆顶的牛跳完,所以放进去的时候要加上堆顶的牛的跳舞时间。

记录最后一头牛跳完的时间。

然后就没了。

#include <bits/stdc++.h>
#define rep(i, a, b) for(register int i = a; i <= b; ++i)
using namespace std;
constexpr int N = 1e4 + 5;
int ans, L, R, n, tmx, d[N];
priority_queue<int, vector<int>, greater<>> q;
inline bool check(int k) {rep(i, 1, k) {q.push(d[i]);}rep(i, k + 1, n) {q.push(d[i] + q.top());q.pop();}while(!q.empty()) {ans = q.top();q.pop();}return ans <= tmx;
}
int main() {cin >> n >> tmx;rep(i, 1, n) cin >> d[i];L = 1, R = n;while(L <= R) {int mid = L + R >> 1;if(check(mid)) {R = mid - 1;}else {L = mid + 1;}}cout << L;return 0;
}
http://www.hskmm.com/?act=detail&tid=37666

相关文章:

  • 搜维尔科技将携手Xsens|Haption|Tesollo|Manus亮相IROS 2025国际智能机器人与系统会议
  • 【做题记录】贪心--提高组
  • 如何炫酷地使用集合划分容斥
  • 简单云计算算法--20251023
  • 处理空输入踩的坑
  • latex输入公式
  • 【为美好CTF献上祝福】 New Star 2025 逆向笔记
  • XXL-JOB(5)
  • 蛋白表达原理与关键要素解析
  • Ramanujan Master Theorem
  • 顾雅南的声音美化课堂
  • C++案例 自定义数组
  • 【周记】2025.10.13~2025.10.19
  • 背包
  • 10.23《程序员修炼之道 从小工到专家》第二章 注重实效的途径 - GENGAR
  • 玩转单片机之智能车小露——LED闪烁实战
  • ord() 函数
  • 2025.10.23总结 - A
  • 大模型 | VLA 初识及在自动驾驶场景中的应用
  • ExPRT.AI如何预测下一个将被利用的漏洞
  • Redis中的分布式锁之SETNX底层实现
  • 攻击模拟
  • 2025家纺摄影公司推荐,南通鼎尚摄影专注产品视觉呈现
  • AI元人文构想的跨学科研究:技术实现与人文影响分析——对自由与责任的再框架化(DeepSeek基于Ai元人文系列文章研究)
  • Python---简易编程解决工作问题
  • 日总结 16
  • 比赛题解 总结
  • DM8 安装包 for linux_x86
  • MPK(Mirage Persistent Kernel)源码笔记(1)--- 基础原理
  • 模拟can通信