wyh學長現在手里有n個物品，這n個物品的重量和價值都告訴你，然后現在讓你從中選取k個，問你在所有可能選取的方案中，最大的單位價值為多少（單位價值為選取的k個物品的總價值和總重量的比值）
輸入描述:
輸入第一行一個整數T(1<=T<=10)
接下來有T組測驗資料，對于每組測驗資料，第一行輸入兩個數n和k(1<=k<=n<=100000)
接下來有n行，每行兩個是a和b，代表這個物品的重量和價值
輸出描述:
對于每組測驗資料，輸出對應答案，結果保留兩位小數
示例1
輸入
1
3 2
2 2
5 3
2 1
輸出
0.75
說明
對于樣例來說，我們選擇第一個物品和第三個物品，達到最優目的
//238ms
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
const double eps = 1e-6;
struct node
{
double w, v, f;
bool operator < (const node &tmp) const
{
return f < tmp.f;
}
}use[maxn];
int main()
{
int t;
cin>>t;
while(t--)
{
int n, k;
cin >> n >> k;
for(int i = 0;i < n; ++i) cin >> use[i].w >> use[i].v;
double res = rand(), res_cal = res + 2;
while(fabs(res_cal - res) > eps)
{
res = res_cal;
for(int i = 0; i < n; ++i)
use[i].f = res * use[i].w - use[i].v;
sort(use, use + n);
double w_use = 0, v_use = 0;
for(int i = 0; i < k; ++i)
w_use += use[i].w, v_use += use[i].v;
res_cal = 1.0 * v_use / w_use;
}
cout << fixed << setprecision(2) << res << endl;
}
return 0;
}
//387ms
#include<bits/stdc++.h>
using namespace std;
int c[100005], v[100005], n, k;
double p[100005];
bool check(double x)
{
for(int i = 0; i < n; i++)
p[i] = v[i] - x * c[i];
sort(p, p + n);
double sum = 0;
for(int i = n - 1; i >= n - k; i--)
sum += p[i];
return sum >= -0.00001;
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++)
scanf("%d%d", &c[i], &v[i]);
double l = 0, r = 200, mid;
while(l <= r)
{
mid = (l + r) / 2;
if(fabs(r - l) < 0.001) break;
if(check(mid)) l = mid;
else r = mid;
}
printf("%.2f\n", mid);
}
return 0;
}
//173ms
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 100;
const double eps = 1e-6;
struct node
{
double w, v, f;
bool operator < (const node &tmp) const
{
return f < tmp.f;
}
}use[maxn];
int main()
{
int t, n, k;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &n, &k);
for(int i = 0;i < n; ++i) scanf("%lf%lf", &use[i].w, &use[i].v);
double res = rand(), res_cal = res + 2;
while(fabs(res_cal - res) > eps)
{
res = res_cal;
for(int i = 0; i < n; ++i)
use[i].f = res * use[i].w - use[i].v;
sort(use, use + n);
double w_use = 0, v_use = 0;
for(int i = 0; i < k; ++i)
w_use += use[i].w, v_use += use[i].v;
res_cal = 1.0 * v_use / w_use;
}
cout << fixed << setprecision(2) << res << "\n";
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/263916.html
標籤：其他
上一篇：最小生成樹
下一篇：1574：矩陣取數游戲