xc01

题解

/ 注册

全部文章 / 题解（共6篇）

题解40 小咪买东西

前言：这是一道01分数规划题，要用二分+验证解决。记枚举元素为x，sum(value)/sum(cost)>=x即满足要求,sum(value)-x*sum(cost)>=0;则sum(value-x *cost)>=0 sum()=>最大的前k项加起来 AC代码&思...

C++ 二分查找

2025-08-17

0 8

题解39 [HDU6231] K-th Number

前言：第M大元素，依然可以用二分+验证解决。现在问题是如何验证。记二分枚举元素位x，则应找到>=x的元素大于k的区间个数。因为这种区间的第k大的数在数组b中一定排在x的前面或一块（相等）。如果区间个数>=m，说明枚举的x<=第m大元素，反之，x>第m大元素。注意：二分查找要...

C++ 二分查找数学

2025-08-17

0 7

题解38 [NOIP2012 提高组] 借教室

前言：具有二分性质，在处理到某个人时，教室数量突然就<0，然后就不能再处理请求了。将处理的订单数作为二分枚举对象依旧是一道二分+验证的题,并且同前缀和与差分结合起来（注意：涉及到对区间大量的+-操作，一定不能直接操作，而是要维护一个差分数组，不然时间直接爆表）思路&AC代码： #...

C++ 二分查找前缀和

2025-08-17

0 8

题解37 [CQOI2010] 扑克牌

思路：一道最值问题，故尝试把组成牌的套数当作二分对象，假设需要组成牌的套数过多就一定组不成（有明显的区分点）。故使用二分枚举+验证，现在重点在于如何验证？这要用到抽屉原理的知识。每套牌不能有重复的，则最多一张joker，如果need>套数，则一定有重复的。且给出的joker数量要足够 AC代码...

C++ 二分查找

2025-08-17

0 7

题解35 烘干（poj3104）二分查找＋验证

题目：有 n 件刚洗完的衣服，其中第 i 件衣服上含有 ai 单位水分。自然晾干的情况下，每件衣服每分钟可以减少 1 单位水分。有一个可以使用的烘***，同一时间仅能容纳最多一件衣服。在使用烘***的情况下，每件衣服每分钟可以减少 k 单位水分。烘***每次使用的工作时间必须是整数分钟，不足...

C++ C 二分查找

2025-08-15

0 10

题解34 【模板】整数域二分

前言：又是一道模板题，我感觉关于边界的问题不好考虑，确定好自己唯一的一种写法就好。我的写法是按照正常思路考虑，然后求<=的最后一个元素时将mid=l+(r-l+1)/2，即(l+r+1)/2，写成r-l可以将让两个int范围边缘的正数相加不超限。后附有二分代码与使用STL函数的代码 AC代码（...

C++ C 二分查找

2025-08-13

0 10