2018 Nowcoder Multi-University Training Contest 5

A. gpa

题意：

有\(n\)门课程，每门课程的学分为\(s_i\)，绩点为\(c_i\)，要求最多删除\(k\)门课程，使得gpa最高。

gpa计算方式如下：

\[\begin{eqnarray*}
gpa = \frac{\sum s_ic_i}{\sum s_i}
\end{eqnarray*}
\]

思路：

首先删去的课程越多，gpa肯定不会变得更差。

所以我们肯定是删去\(k\)门课程。

考虑二分答案，check的时候要满足：

\[\begin{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\n", 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\n", 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\n", 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\n", res);

		}

	}

	return 0;

}

巴特西

2018 Nowcoder Multi-University Training Contest 5

最新文章

热门文章