Select solution language
Write solution here.
Ta muốn chọn $k$ món sao cho: $\frac{v_1 + v_2 + \cdots + v_k}{w_1 + w_2 + \cdots + w_k}$ lớn nhất.
Biến đổi bài toán thành kiểm tra với một $X$ cho trước, có chọn được $k$ món sao cho:
$$
\frac{v_1 + v_2 + \cdots + v_k}{w_1 + w_2 + \cdots + w_k} \geq X
$$
$$
\Leftrightarrow \quad v_1 - X \cdot w_1 + v_2 - X \cdot w_2 + \cdots + v_k - X \cdot w_k \geq 0
$$
Đến đây ta dùng tìm kiếm nhị phân để tìm giá trị lớn nhất $X$ thoả mãn điều kiện trên.
**Code:**
```cpp
/*
/\_/\
(= ._.)
/ >0 \>1
*/
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define int long long
#define el cout<<"\n"
#define pii pair<int32_t,int32_t>
#define pll pair<int,int>
#define sz(x) (int32_t)(x).size()
#define all(x) (x).begin(),(x).end()
#define f0(i,n) for(int32_t i=0;i<n;i++)
#define f1(i,n) for(int32_t i=1;i<=n;i++)
#define fz(i,a,n,z) for(int32_t i=a;i<n;i+=z)
#define rep(i,a,n,z) for(int32_t i=a;i>n;i-=z)
#define file(name) if(fopen(name".inp","r")){freopen(name".inp","r",stdin);freopen(name".out","w",stdout);}
template<typename... T>
void in(T&... args) { ((cin >> args), ...); }
template <typename T>
bool minimize(T& a, const T& b) {
return b < a ? (a = b, true) : false;
}
template <typename T>
bool maximize(T& a, const T& b) {
return a < b ? (a = b, true) : false;
}
const int MAXN = 1e6+5;
const int mod =1e9+7;
inline void add(int &a,int b){
a+=b;
if(a >= mod) a-=mod;
if(a < 0) a+=mod;
}
vector<pair<int,int>> a;
int n,k;
bool check(double mid){
vector<double> b;
for(auto [v,w] : a) b.push_back(v-mid*w);
sort(b.rbegin(),b.rend());
double ans=0;
f0(i,k) ans+=b[i];
return ans >= 0;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
file("TEST");
in(n,k);
a.resize(n);
for(auto &[v,w] : a) in(v,w);
double l=0,r=1e18;
f0(_,100){
double mid=(l+r)/2.0;
if(check(mid)) l=mid;
else r=mid;
}
cout<<fixed<<setprecision(10)<<l;
}
```
Vinhzn08
Created at
0 likes