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

KC 喝咖啡/书的复制/奶牛晒衣服/ 切绳子

news 来源：原创 2025/7/15 5:10:22

二分的解题思路：

常解决最小值最大化和最大值最小化问题

步骤解析

确定答案范围
设定初始左边界 left 和右边界 right，确保解在此区间内。例如：
- 求最小最大值时，left 可取单个元素的最大值，right 取所有元素总和。
- 求最大最小值时，left 可取可能的最小值，right 取可能的最大值。
二分循环
当 left < right 时，执行以下步骤：
- 计算中间值：mid = (left + right) // 2（或向上取整避免死循环）。
- 判定可行性：设计辅助函数 check(mid)，判断当前值是否满足条件。
  - 若满足，调整边界以寻找更优解（如缩小右边界）。
  - 若不满足，调整左边界以尝试更大值。
收敛结果
循环结束时，left 即为所求的最优解。

关键点

单调性：问题必须满足“若 mid 可行，则所有比 mid 大（或小）的值也可行”的单调性。
边界调整：需根据问题类型调整边界移动方式：
- 最小化问题：若 mid 可行，令 right = mid；否则 left = mid + 1。
- 最大化问题：若 mid 可行，令 left = mid；否则 right = mid - 1（此时 mid 应向上取整）。
避免死循环：注意处理相邻边界情况，合理选择取整方式。

E - KC 喝咖啡

Description

话说 KC 和 SH 在福州的时候常常跑去 85°C 喝咖啡或者其他的一些什么东西。

这天，KC 想要喝一杯咖啡，服务员告诉他，现在有 nn 种调料，这杯咖啡只可以加入其中的 mm 种（当然 KC 一定会加入 mm 种，不会加入少于 mm 种的调料），根据加入的调料不同，制成这杯咖啡要用的时间也不同，得到的咖啡的美味度也不同。

KC 在得知所有的 nn 种调料后，作为曾经的化竞之神的他，马上就知道了所有调料消耗的时间 cici 以及调料的美味度 vivi。由于 KC 急着回去刷题，所以他想尽快喝到这杯咖啡，但他又想喝到美味的咖啡，所以他想出了一个办法，他要喝到 ∑vi∑ci∑ci∑vi 最大的咖啡，也就是单位时间的美味度最大的咖啡。

现在，KC 把调料信息告诉了 SH，要 SH 帮他算出喝到的咖啡的 ∑vi∑ci∑ci∑vi，但 SH 不想帮 KC 算这东西，于是 KC 就只能拜托你来算了。

注释：∑∑ 表示求和，所以 ∑vi∑ci∑ci∑vi 表示美味度的总和除以消耗时间的总和。

Input

输入数据共三行。

第一行为一个整数 n,mn,m，表示调料种数和能加入的调料数。

接下来两行，每行为 nn 个数，第一行第 ii 个整数表示调料 ii 的美味度 vivi，第二行第 ii 个整数表示调料 ii 消耗的时间 cici。

Output

一个实数 TT，表示 KC 喝的咖啡的最大 ∑vi∑ci∑ci∑vi，保留三位小数。

Sample 1

Inputcopy	Outputcopy
3 2 1 2 3 3 2 1	1.667

Hint

样例 1 解释：

KC 选 22 号和 33 号调料，∑vi∑ci=2+32+1=1.667∑ci∑vi=2+12+3=1.667。

可以验证不存在更优的选择。

数据范围：

对 20%20% 的数据：1≤n≤51≤n≤5。

对 50%50% 的数据：1≤n≤101≤n≤10。

对 80%80% 的数据：1≤n≤501≤n≤50。

对 100%100% 的数据：1≤n≤200,1≤m≤n,1≤c[i],v[i]≤1×1041≤n≤200,1≤m≤n,1≤c[i],v[i]≤1×104。

数据保证答案不超过 10001000。

思路：

可能有人跟我一样，虽然一开始想到了二分，但图方便先直接纯贪心（两个比值大的加上面就是最佳的），但这样是错误的。

举个反例：

3 2  
4 3 5  
1 2 3

正确输出：2.333
原代码输出：2.250

- 调料信息：
  - 调料1：v=4, c=1 → 比值 4.0
  - 调料2：v=3, c=2 → 比值 1.5
  - 调料3：v=5, c=3 → 比值 ≈1.666
贪心策略的选择
- 按比值排序：调料1（4.0）→ 调料3（1.666）→ 调料2（1.5）。
- 选择前两个：调料1和调料3。
- 总比值：(4+5)/(1+3) = 9/4 = 2.25。
实际最优选择
- 选择调料1和调料2。
- 总比值：(4+3)/(1+2) = 7/3 ≈ 2.333。

所以还是要用二分加贪心：

最大总比值问题需通过二分法寻找最优解。设定目标比值 k，检查是否存在 m 个物品使得 ∑(vi−k⋅ci)≥0。若存在，则增大 k；否则减小 k。这种方法确保正确性。

二分框架：通过二分法确定最大比值 k，范围初始化为 [0,106]。

检查函数：对每个 k，计算所有物品的 vi−k⋅ci，取最大的 m 个求和。若和 ≥0，说明存在更优解。

代码：


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
struct MyStruct
{int x, y;
}a[205];
int n, m;
bool Check(double mid) {vector<double> b(n);for (int i = 0; i < n; i++) {b[i] = a[i].x - mid * a[i].y;}sort(b.begin(),b.end(), greater<double>());double w = 0;for (int i = 0; i < m; i++) {w += b[i];}return w >= 0;
}
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n >> m;for (int i = 0; i < n; i++) {cin >> a[i].x;}for (int i = 0; i < n; i++) {cin >> a[i].y;}double max_p = 1000;//题目说的不超过1000double min_p = 0, mid;while (max_p - min_p >= 0.001) {mid = (max_p + min_p) / 2;if (Check(mid)) {min_p = mid;}else {max_p = mid;}}double w = (min_p + max_p) / 2;cout << fixed << setprecision(3) << w << endl;return 0;
}//纯贪心（算排序两个比值大的，然后按序加进去是错误的）
// 反例：
//3 2
//4 3 5
//1 2 3//
//#define _CRT_SECURE_NO_WARNINGS
//#include<stdio.h>
//#include<iostream>
//#include<bits/stdc++.h>
//using namespace std;
//struct MyStruct
//{
//	int x, y;
//	double k;
//}a[205];
//int n, m;
//double w;
//int x = 0, y = 0;
//
//int main() {
//	ios::sync_with_stdio(false);        // 禁用同步
//	cin.tie(nullptr);                   // 解除cin与cout绑定
//	cin >> n >> m;
//	for (int i = 0; i < n; i++) {
//		cin >> a[i].x;
//	}
//	for (int i = 0; i < n; i++) {
//		cin >> a[i].y;
//		a[i].k = (double)a[i].x / (double)a[i].y;
//	}
//	sort(a, a + n, [](const MyStruct& a, const MyStruct& b) {
//		return a.k > b.k;
//		});
//	int sum = 0;
//	for (int i = 0; i < m; i++) {
//		x += a[i].x;
//		y += a[i].y;
//		sum++;
//	}
//	w = (double)x / (double)y;
//	cout << fixed<<setprecision(3)<<w << endl;
//	return 0;
//}

C - 书的复制

Background

大多数人的错误原因：尽可能让前面的人少抄写，如果前几个人可以不写则不写，对应的人输出 0 0 。

不过，已经修改数据，保证每个人都有活可干。

Description

现在要把 mm 本有顺序的书分给 kk 个人复制（抄写），每一个人的抄写速度都一样，一本书不允许给两个（或以上）的人抄写，分给每一个人的书，必须是连续的，比如不能把第一、第三、第四本书给同一个人抄写。

现在请你设计一种方案，使得复制时间最短。复制时间为抄写页数最多的人用去的时间。

Input

第一行两个整数 m,km,k。

第二行 mm 个整数，第 ii 个整数表示第 ii 本书的页数。

Output

共 kk 行，每行两个整数，第 ii 行表示第 ii 个人抄写的书的起始编号和终止编号。 kk 行的起始编号应该从小到大排列，如果有多解，则尽可能让前面的人少抄写。

Sample 1

Inputcopy	Outputcopy
9 3 1 2 3 4 5 6 7 8 9	1 5 6 7 8 9

Hint

1≤k≤m≤5001≤k≤m≤500。

思路：

这题就是简单的二分写的，但唯一值得注意的应该是答案的打印。因为他要尽可能的让前面的人少抄，所以我是递归，从后面开始遍历，让后面的人多抄。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int max_l = 0, min_r = 0;
int a[505];
int m, k;
bool PanDuan(int q) {int j = 0;int sum = 1;for (int i = 1; i <= m; i++) {if (a[i] - a[j] > q) {sum++;j = i - 1;}}return sum <= k;
}
void Print(int sum,int i,int pp) {if (i <= 0) {while (sum < k) {cout << 0 << " " << 0 << endl;sum++;}return;}int j = i;while (j >= 1&&a[i]-a[j-1]<=pp) {j--;}sum++;Print(sum, j, pp);cout << j + 1 << " " << i << endl;
}
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> m >> k;for (int i = 1; i <= m; i++) {cin >> a[i];if (a[i] > min_r) {min_r = a[i];}a[i] += a[i - 1];}max_l = a[m];while (max_l > min_r) {int mid = min_r + (max_l - min_r) / 2;if (PanDuan(mid)) {max_l = mid;}else {min_r = mid + 1;}}Print(0, m,min_r);return 0;
}

奶牛晒衣服

Background

熊大妈决定给每个牛宝宝都穿上可爱的婴儿装。但是由于衣服很湿，为牛宝宝晒衣服就成了很不爽的事情。于是，熊大妈请你（奶牛）帮助她完成这个重任。

Description

一件衣服在自然条件下用一秒的时间可以晒干 a 点湿度。抠门的熊大妈只买了一台烘衣机。使用用一秒烘衣机可以让一件衣服额外烘干 b 点湿度（一秒晒干 a+b湿度），但在同一时间内只能烘一件衣服。现在有 n 件衣服，第 ii 衣服的湿度为 wi（保证互不相同），要你求出弄干所有衣服的最少时间（湿度为 0 为干）。i

Input

第一行三个整数，分别为 n,a,b。
接下来 2 到 n+1 行，第 i 行输入 wi。

Output

一行，弄干所有衣服的最少时间。

Sample 1

Inputcopy	Outputcopy
3 2 1 1 2 3	1

Hint

样例解释

让机器烘第三件衣服即可一秒完成。

数据范围

1≤wi,a,b,n≤5×105

思路：

这题也是二分，我感觉这个要注意的是不够晒干/烘干的单位时间的湿度要当作1来处理。

还可能有点难的是判断，我是将没件超出晒干时间的都当作使用烘干机的时间。

代码：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n, a, b;
int p[500005];
int max_p=0, min_p=1;
bool Check(int mid) {int sum = 0;for (int i = 0; i < n; i++) {if (mid * a < p[i]) {sum += (p[i] - mid * a) /b + ((p[i] - mid * a) % b == 0 ? 0 : 1);}}return sum <= mid;
}
int main(){ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n >> a >> b;for (int i = 0; i < n; i++) {cin >> p[i];if (p[i] > max_p) {max_p = p[i];}}max_p = max_p / a + (max_p % a == 0 ? 0 : 1);while (max_p > min_p) {int mid = (max_p + min_p) / 2;if (Check(mid)) {max_p = mid;}else {min_p = mid + 1;}}cout << min_p << endl;return 0;
}

F - 切绳子

Description

有 NN 条绳子，它们的长度分别为 LiLi。如果从它们中切割出 KK 条长度相同的绳子，这 KK 条绳子每条最长能有多长？答案保留到小数点后 22 位(直接舍掉 22 位后的小数)。

Input

第一行两个整数 NN 和 KK，接下来 NN 行，描述了每条绳子的长度 LiLi 。

Output

切割后每条绳子的最大长度。答案与标准答案误差不超过 0.010.01 或者相对误差不超过 1%1% 即可通过。

Sample 1

Inputcopy	Outputcopy
4 11 8.02 7.43 4.57 5.39	2.00

Hint

对于 100%100% 的数据 0<Li≤100000.00,0<n≤10000,0<k≤100000<Li≤100000.00,0<n≤10000,0<k≤10000

这题应该算是标准的二分答案了，只不过结束判断，是max-min<0.001

代码：


#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
double a[10005];
int n, m;
bool Check(double mid) {int w=0;for (int i = 0; i < n; i++) {w += (int)(a[i] / mid);}return w >= m;
}
int main() {ios::sync_with_stdio(false);        // 禁用同步cin.tie(nullptr);                   // 解除cin与cout绑定cin >> n >> m;double max_p = 0;//题目说的不超过1000double min_p = 0, mid;for (int i = 0; i < n; i++) {cin >> a[i];if (max_p < a[i]) {max_p = a[i];}}while (max_p - min_p >= 0.001) {mid = (max_p + min_p) / 2;if (Check(mid)) {min_p = mid;}else {max_p = mid;}}double w = (min_p + max_p) / 2;cout << fixed << setprecision(2) << w << endl;return 0;
}

二分的解题思路：

常解决最小值最大化和最大值最小化问题

步骤解析

关键点

E - KC 喝咖啡

Description

Input

Output

Sample 1

Hint

思路：

代码：

C - 书的复制

Background

Description

Input

Output

Sample 1

Hint

思路：

代码：

奶牛晒衣服

Background

Description

Input

Output

Sample 1

Hint

样例解释

数据范围

思路：

代码：

F - 切绳子

Description

Input

Output

Sample 1

Hint

这题应该算是标准的二分答案了，只不过结束判断，是max-min<0.001

代码：

相关文章：