2024.12.22 周日

Q1. 1100

You are playing a computer game. The current level of this game can be modeled as a straight line. Your character is in point $0$ of this line. There are $n$ monsters trying to kill your character; the $i$-th monster has health equal to $a_i$ and is initially in the point $x_i$.

Every second, the following happens:

• first, you fire up to $k$ bullets at monsters. Each bullet targets exactly one monster and decreases its health by $1$. For each bullet, you choose its target arbitrary (for example, you can fire all bullets at one monster, fire all bullets at different monsters, or choose any other combination). Any monster can be targeted by a bullet, regardless of its position and any other factors;
• then, all alive monsters with health $0$ or less die;
• then, all alive monsters move $1$ point closer to you (monsters to the left of you increase their coordinates by $1$, monsters to the right of you decrease their coordinates by $1$). If any monster reaches your character (moves to the point $0$), you lose.

Can you survive and kill all $n$ monsters without letting any of them reach your character?

Q2. 1100

Petya has an array $a_i$ of $n$ integers. His brother Vasya became envious and decided to make his own array of $n$ integers.

To do this, he found $m$ integers $b_i$ ($m\ge n$), and now he wants to choose some $n$ integers of them and arrange them in a certain order to obtain an array $c_i$ of length $n$.

Vasya wants to make his array as different as possible from Petya's array. Specifically, he wants the total difference $D = \sum_{i=1}^{n} |a_i - c_i|$ to be as large as possible.

Help Vasya find the maximum difference $D$ he can obtain.

------------------------独自思考分割线------------------------

• 2道贪心

A1.

1. 设定距离数组：距离为 $i$ 时怪物血量总和。检查每一个 $i*k<=pre[i]$。

A2.

1. 一道有意思的贪心，想了很久，证明略难..

------------------------代码分割线------------------------

A1.

#include <bits/stdc++.h>
#define int long long //
#define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, k;
    cin >> n >> k;
    vector<int> a(n), x(n), pre(n + 1);
    for (int &x : a)
        cin >> x;
    for (int &x : x)
        cin >> x;
    for (int i = 0; i < n; i++)
        pre[abs(x[i])] += a[i];
    bool res = 1;
    for (int i = 1; i <= n; i++)
    {
        pre[i] += pre[i - 1];
        if (pre[i] > k * i)
            res = 0;
    }
    cout << (res ? "YES" : "NO") << endl;
}

A2.

#include <bits/stdc++.h>
#define int long long //
// #define endl '\n'     // 交互/调试 关
using namespace std;
#define bug(BUG) cout << "bug:# " << (BUG) << endl
#define bug2(BUG1, BUG2) cout << "bug:# " << (BUG1) << " " << (BUG2) << endl
#define bug3(BUG1, BUG2, BUG3) cout << "bug:# " << (BUG1) << ' ' << (BUG2) << ' ' << (BUG3) << endl
void _();
signed main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cout << fixed << setprecision(6);
    int T = 1;
    cin >> T;
    while (T--)
        _();
    return 0;
}

void _()
{
    int n, m;
    cin >> n >> m;
    struct Node
    {
        /* data */
        int x, i;
    };

    vector<Node> a(n + 1);
    vector<int> b(m + 1), res(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i].x, a[i].i = i;
    for (int i = 1; i <= m; i++)
        cin >> b[i];
    sort(a.begin() + 1, a.end(), [](Node &a, Node &b)
         { return a.x < b.x; });
    sort(b.begin() + 1, b.end());
    int la = 1, ra = n, lb = 1, rb = m;
    while (la <= ra)
    {
        if (abs(a[la].x - b[rb]) > abs(a[ra].x - b[lb]))
            res[la] = b[rb], la++, rb--;
        else
            res[ra] = b[lb], ra--, lb++;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans += abs(a[i].x - res[i]);
    // cout << res[i] << ' ';
    cout << ans << endl;
}