建议倍增
常数极小
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
const double eps = 1e-5;
int n, k;
double a[N], b[N];
double c[N];
bool check(double x)
{
double res = 0;
for (int i = 1; i <= n; ++i) c[i] = a[i] - x * b[i];
sort(c + 1, c + 1 + n);
for (int i = k + 1; i <= n; ++i) res += c[i];
return res >= 0;
}
int main()
{
while (scanf("%d%d", &n, &k), n || k) {
for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
for (int i = 1; i <= n; ++i) scanf("%lf", &b[i]);
double l = 0, p = 1;
while (check(l + p)) l += p, p *= 2;
while (fabs(p) > eps) {
if (check(l + p)) l += p;
p /= 2;
}
printf("%.0lf\n", l * 100);
}
return 0;
}
Update on Feb. 4th, 2022
建议二分
常数更小
之前倍增常数较小是因为答案其实不会超过 $1\times 100$,而唯一的一篇题解的 $r$ 初值为 $10^9$,因此二分常数很大。
实际上当二分确定了一个正确的上界后,二分的常数比倍增还小,因为答案通常比较靠近上界。而倍增常数小的时候通常是答案比较靠近下界的时候。
从这个角度来看,之前的倍增之所以比二分常数小,其本质原因在于,当答案区间取 $[0,10^9]$ 的时候,答案靠近下界而不是上界,此时倍增比二分常数小。
参考代码
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 1010;
const double eps = 1e-4;
int n, k;
double a[N], b[N];
double c[N];
bool check(double x)
{
double res = 0;
for (int i = 1; i <= n; ++i) c[i] = a[i] - x * b[i];
sort(c + 1, c + 1 + n);
for (int i = k + 1; i <= n; ++i) res += c[i];
return res >= 0;
}
int main()
{
while (scanf("%d%d", &n, &k), n || k) {
for (int i = 1; i <= n; ++i) scanf("%lf", &a[i]);
for (int i = 1; i <= n; ++i) scanf("%lf", &b[i]);
double l = 0, r = 1, mid;
while (r - l > eps) {
mid = (l + r) / 2;
if (check(mid)) l = mid;
else r = mid;
}
printf("%.0lf\n", round(l * 100));
}
return 0;
}
liu cheng nb!!!
问个小问题while (check(l + p)) l += p, p *= 2;好像没有用吧,我感觉这个比值不可能大于1所以不会执行这一步?(害怕
有用,样例就用了
没有吧,删掉这句话似乎还是可以过样例而且可以a
啊确实,我应该是受了另一篇题解的影响,以为答案可能很大
比值不会大于一的话可以把这句话删掉然后初始值设为0.5,也可以A
题解更新了,要不要看看
鼓掌ing