A. gpa
题意：
有(n)门课程，每门课程的学分为(s_i)，绩点为(c_i)，要求最多删除(k)门课程，使得gpa最高。
gpa计算方式如下：
[egin{eqnarray*}
gpa = frac{sum s_ic_i}{sum s_i}
end{eqnarray*}
]
思路：
首先删去的课程越多，gpa肯定不会变得更差。
所以我们肯定是删去(k)门课程。
考虑二分答案，check的时候要满足：
[egin{eqnarray*}
gpa &leq& frac{sum s_ic_i}{sum s_i} \
gpa cdot sum s_i &leq& sum s_ic_i \
sum s_i cdot gpa &leq& sum s_ic_i \
sum s_i cdot (gpa - c_i) &leq& 0
end{eqnarray*}
]
那么check的时候贪心选取(n - k)个即可。
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define N 100010
#define pii pair <int, int>
#define fi first
#define se second
const db eps = 1e-10;
int n, k; pii a[N];
bool ok(db x) {
vector <db> vec;
for (int i = 1; i <= n; ++i) {
vec.push_back(a[i].fi * (x - a[i].se));
}
sort(vec.begin(), vec.end());
db tot = 0;
for (int i = 0; i < n - k; ++i) {
tot += vec[i];
}
return tot <= 0 || fabs(tot - 0) < eps;
}
int main() {
while (scanf("%d%d", &n, &k) != EOF) {
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i].fi);
}
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i].se);
}
db l = 0, r = 1e3, res = 0;
while (fabs(r - l) >= eps) {
db mid = (l + r) / 2;
if (ok(mid)) {
l = mid;
res = mid;
} else {
r = mid;
}
}
printf("%.10f
", res);
}
return 0;
}
G. max
题意：
给出(c)和(n)，要求找到一对((a, b))满足(1 leq a, b leq n)使得(gcd(a, b) = c)并且最大化(a cdot b)
思路：
- (c > n)时无解
- (c = n)时选择((n, n))
- (c < n)时在([1, frac{n}{c}])中选取两个互质的数再分别乘上(c)
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll c, n;
int main() {
while (scanf("%lld%lld", &c, &n) != EOF) {
if (c > n) {
puts("-1");
continue;
}
ll x = n / c;
ll res = c * c;
if (x > 1) {
res *= x * (x - 1);
}
printf("%lld
", res);
}
return 0;
}
J. plan
题意：
有(n)个人去住宿，双人房的价格为(p_2)， 三人房的价格为(p_3)，要求将(n)个人全都安排好住宿的最小代价是多少，不一定恰好住满。
思路：
大范围直接除2， 除3， 小范围暴力dp一下。
代码：
#include <bits/stdc++.h>
using namespace std;
#define N 1000010
#define ll long long
#define ll long long
ll n, p2, p3;
ll f[N];
ll DFS(int x) {
if (x <= 0) {
return 0;
}
if (f[x] != -1) {
return f[x];
}
return f[x] = min(p2 + DFS(x - 2), p3 + DFS(x - 3));
}
int main() {
while (scanf("%lld%lld%lld", &n, &p2, &p3) != EOF) {
memset(f, -1, sizeof f);
if (n <= 1000000) {
printf("%lld
", DFS(n));
} else {
ll res = 1e18;
ll m;
for (int i = 0; i < 1000000; ++i) {
m = n - i;
res = min(res, p2 * (m / 2) + DFS(i + m % 2));
res = min(res, p3 * (m / 3) + DFS(i + m % 3));
}
printf("%lld
", res);
}
}
return 0;
}