欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

牛客 A.gpa(01分数规划)

程序员文章站 2022-05-21 19:58:18
...

链接:https://www.nowcoder.com/acm/contest/143/A
来源:牛客网
 

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

Kanade selected n courses in the university. The academic credit of the i-th course is s[i] and the score of the i-th course is c[i].

At the university where she attended, the final score of her is 牛客 A.gpa(01分数规划)

Now she can delete at most k courses and she want to know what the highest final score that can get.

输入描述:

The first line has two positive integers n,k

The second line has n positive integers s[i]

The third line has n positive integers c[i]

输出描述:

Output the highest final score, your answer is correct if and only if the absolute error with the standard answer is no more than 10-5

示例1

输入

复制

3 1
1 2 3
3 2 1

输出

复制

2.33333333333

说明

Delete the third course and the final score is 

备注:

1≤ n≤ 105

0≤ k < n

1≤ s[i],c[i] ≤ 103

 

 

 

题目大意:

给定 n 门课以及它们的学分和绩点,定义总绩点是所有课的加权平均数,给定一个数 k, 你可以删除最多 k 门课,求你的总绩点最大能到多少
 

 

 

 

分析:

牛客 A.gpa(01分数规划)

上面是牛客的官方题解,其实就是移项, 然后按照 c[i] - D 排一下序 然后求前几个的和

 

 

 

 

AC代码:

 /*************************************************
       Author       :	NIYOUDUOGAO
       Last modified:	2018-08-03 10:21
       Email        :	aaa@qq.com
       Filename     :	t1.cpp
 *************************************************/
#include <bits/stdc++.h>
#define mset(a, x) memset(a, x, sizeof(a))
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int N = 1e7 + 5;
int s[N], c[N];
double t[N];
int n, k;
struct node {
	int s, c;
}a[N];
bool cmp(int x, int y) {
	return x > y;
} 
bool judge(double d) {
	double res = 0;
	for (int i = 0; i < n; i++) {
		t[i] = a[i].s * (a[i].c - d);
	}
	sort(t, t + n, cmp);
	for (int i = 0; i < n - k; i++) {
		res += t[i];
	}
	if (res >= 0) return 1;
	return 0;
}
int main() {
	scanf("%d%d", &n, &k); 
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i].s);
	}
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i].c);
	}
	double l = 0, r = 1001;
	double ans = 0;
	while (r - l >= 1e-8) {
		double mid = (l + r) / 2.0;
		if (judge(mid)) {
			ans = mid;
			l = mid + 0.000000001;
		} else {
			r = mid - 0.000000001;
		}
	}
	printf ("%.11lf\n", ans);
	return 0;
}