【全网首发】洛谷P1570 KC喝咖啡

2023-12-24 13:32:38

前言

如果你不会做这题,就跟着学学吧,想要了解二分,请看

洛谷KCP1570? 喝咖啡

题目描述

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

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

KC 在得知所有的n种调料后,作为曾经的化竞之神的他,马上就知道了所有调料消耗的时间 c _ i以及调料的美味度v _ i。由于 KC 急着回去刷题,所以他想尽快喝到这杯咖啡,但他又想喝到美味的咖啡,所以他想出了一个办法,他要喝到 dfrac{sum v _ i}{sum c _ i}?最大的咖啡,也就是单位时间的美味度最大的咖啡。

现在,KC 把调料信息告诉了 SH,要 SH 帮他算出喝到的咖啡的 dfrac{sum v _ i}{sum c _ i},但 SH 不想帮 KC 算这东西,于是 KC 就只能拜托你来算了。

注释:sum表示求和,所以 dfrac{sum v _ i}{sum c _ i}?表示美味度的总和除以消耗时间的总和。

输入格式

输入数据共三行。

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

接下来两行,每行为 n个数,第一行第 i?个整数表示调料 i?的美味度 v _ i,第二行第 $i$ 个整数表示调料i消耗的时间 c _ i。

输出格式

一个实数 T表示 KC 喝的咖啡的最大dfrac{sum v _ i}{sum c _ i},保留三位小数。

样例 #1

样例输入 #1
3 2
1 2 3
3 2 1
?样例输出 #1
1.667


解题思路

一般最先想到的方法是把物品按照单位价值进行排序,从大到小地贪心进行选取。但是很明显这样去贪心很容易举出反例,于是我们考虑套用二分+贪心来解决。我们可以直接二分答案,区间l取0、r取单个物品的最大价值(注意精度开double),然后对于我们二分出的值x,关键是如何check判断,稍稍运用下数学转换公式:sigma(vi)/sigma(ci)>=x,变形推导出sigma(vi-x*ci)>=0。因此,可以对vi-x*ci进行贪心排序选取前m个,最后只要判断这m个值的和是否大于等于0就ok了。

设最终答案为R,x[i]为0或1,则 Σ(v[i]*x[i]) / Σ(c[i]*x[i]) = R

即 Σ(v[i]*x[i]) - Σ(c[i]*x[i]*R) =0

即 Σ[(v[i]*x[i]) - (c[i]*x[i]*R)] =0

设 f(R)= Σ[(v[i]*x[i]) - (c[i]*x[i]*R)]

二分R,求f(R)=0

当f(R)<0时,R偏大

当f(R)>0时,R偏小

计算每一对 v[i]- (c[i]*R),排序求前m大的和即为f(R) 。

题目本质上是考虑函数 y = sigma(vi) - x * sigma(ci), 使得y尽可能的接近于0.

我们可以给定x, 然后考虑是否存在一种取数方案,使得y > 0

如果存在某种取数方案使得y > 0, 则说明在这种的取数方案下,x还可以继续放大,使得y更加接近于0.(l=mid)

否则,x还可以继续缩小,即(r = mid)

想到了二分答案+分数规划,可是却难在了只能选m种调料这里

看完解析后--> 观察推出来的式子 x为当前二分值

Σ(vi-x*ci)>=0

那么我们可以对调料按照vi-x*ci进行排序,贪心的选前m个

如果最后选的和>=0 说明x合法

AC:

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb(x) push_back(x)
const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
using namespace std;
typedef pair<int, int>pii;
int n, m;
map<int, int>mp;        
double a[500005],b[N],c[N];
string s;
vector<int>g;
inline int read() {
	int w = 1, s = 0; char ch = getchar();
	for (; ! isdigit(ch); ch = getchar()) if(ch == '-') w = - 1;
	for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + ch -'0';
	return s * w;
}
bool check(double x){double sum=0;
	for(int i=1;i<=n;i++){
		c[i]=a[i]-b[i]*x;
	}
	sort(c+1,c+n+1,greater<int>());
	for(int i=1;i<=m;i++)sum+=c[i];
	return sum>=0;
}
void solve () {
	n=read();m=read();
	for(int i=1;i<=n;i++)a[i]=read();
	for(int i=1;i<=n;i++)b[i]=read();
	double  l=0,r=1e9;
	while(r-l>1e-8){
		double mid=(l+r)/2.0;
		if(check(mid))l=mid;
		else r=mid;
	}	
	printf("%.3lf\n",r);
	
}
signed main () {
	int T = 1; 
	std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	//	T = read ();
	// cin>>T;
	while (T --) solve ();
	return 0;
}

如果你喜欢或想了解一下其他的算法,可以看看以下这些:

前缀和与差分:

C++:第九讲前缀和与差分-CSDN博客

贪心:

C++:第八讲贪心算法1-CSDN博客

排序:

C++:第七讲冒泡排序-CSDN博客

函数:

C++第6讲max和min函数_c++ min函数-CSDN博客

C++第五讲函数初步-CSDN博客

for循环&数组:

C++第四讲for循环及数组-CSDN博客

if语句&else语句及运算:

C++第三讲:C++中的逻辑运算符及if else语句-CSDN博客

基础:

C++第二讲输入与输出-CSDN博客

C++第一讲认识C++编译器-CSDN博客

最后认识一下,我是爱编程的喷火龙廖,我们有缘再见!

文章来源:https://blog.csdn.net/2301_81328824/article/details/135179758
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。