AtCoder Beginner Contest 376（A，B，C，D，E）（模拟，贪心，bfs，堆）

比赛链接

A题

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, c;
int a[N];
void solve()
{
    cin >> n >> c;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    int ans = 1, now = a[1];
    for (int i = 2; i <= n; i++)
    {
        if (a[i] - now >= c)
        {
            ans++;
            now = a[i];
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}

B题

思路

$n$和$q$的大小只有$100$。在每一次询问时，直接暴力枚举向左移动还是向右移动即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, q;
void solve()
{
    cin >> n >> q;
    int L = 1, R = 2;
    int ans = 0;
    while (q--)
    {
        char h;
        int t;
        cin >> h >> t;
        if (h == 'L')
        {
            bool ok = false;
            bool tmp = false;
            for (int i = 1, idx = L; i <= n; i++, idx++)
            {
                if (idx == n + 1)
                    idx = 1;
                if (idx == R)
                    ok = true;
                if (idx == t)
                {
                    if (!ok)
                        ans += (i - 1);
                    else
                        tmp = true;
                }
            }
            if (tmp)
            {
                for (int i = 1, idx = L; i <= n; i++, idx--)
                {
                    if (idx == 0)
                        idx = n;
                    if (idx == t)
                    {
                        ans += (i - 1);
                    }
                }
            }
            L = t;
        }
        else
        {
            bool ok = false;
            bool tmp = false;
            for (int i = 1, idx = R; i <= n; i++, idx++)
            {
                if (idx == n + 1)
                    idx = 1;
                if (idx == L)
                    ok = true;
                if (idx == t)
                {
                    if (!ok)
                        ans += (i - 1);
                    else
                        tmp = true;
                }
            }
            if (tmp)
            {
                for (int i = 1, idx = R; i <= n; i++, idx--)
                {
                    if (idx == 0)
                        idx = n;
                    if (idx == t)
                    {
                        ans += (i - 1);
                    }
                }
            }
            R = t;
        }
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}

C题

思路

将$a$和$b$排序之后，直接从大到小贪心即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n;
int a[N], b[N];
void solve()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    for (int i = 1; i < n; i++)
    {
        cin >> b[i];
    }
    sort(a + 1, a + 1 + n);
    sort(b + 1, b + n);
    int cnt = 0;
    int idx = n - 1;
    for (int i = n; i >= 1; i--)
    {
        if (idx > 0 && a[i] <= b[idx])
        {
            idx--;
            cnt++;
        }
    }
    if ((n - cnt) > 1)
    {
        cout << -1 << endl;
    }
    else
    {
        int idx = n - 1;
        int op = n;
        for (int i = n; i >= 1; i--)
        {
            if (a[i] > b[idx])
            {
                op = i;
                break;
            }
            else
                idx--;
        }
        cout << a[op] << endl;
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}

D题

思路

跑一遍bfs，直到第二次找到$1$号节点。如果能找到，则打印最短距离，否则打印$-1$。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, m;
bool st[N];
vector<int> mp[N];
void solve()
{
    cin >> n >> m;
    for (int i = 1, a, b; i <= m; i++)
    {
        cin >> a >> b;
        mp[a].push_back(b);
    }
    queue<pii> q;
    q.push({1, 0});
    st[1] = true;
    int ans = 0;
    while (q.size())
    {
        int u = q.front().first;
        int d = q.front().second;
        q.pop();
        for (int j : mp[u])
        {
            if (j == 1)
            {
                ans = d + 1;
                cout << ans << endl;
                return;
            }
            if (st[j])
                continue;
            st[j] = true;
            q.push({j, d + 1});
        }
    }
    cout << -1 << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    // cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}

E题

思路

按照$a$的大小对两个数组进行从小到大排序。

枚举$a_k\sim a_n$，也就是枚举$ma{x}_{i\in S}a[i]$。

在枚举的过程中，用堆来维护$b$数组的前$k$小数即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> pii;
const int N = 2e5 + 5, M = 1e6 + 5;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f3f3f3f3f;

int n, k;
struct node
{
    int a, b;
} p[N];
bool cmp(node x, node y)
{
    if (x.a != y.a)
        return x.a < y.a;
    return x.b < y.b;
}
void solve()
{
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].a;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i].b;
    }
    sort(p + 1, p + 1 + n, cmp);
    int ans = inf;
    int res = 0;
    priority_queue<int, vector<int>, less<int>> q;
    for (int i = 1; i <= k; i++)
    {
        res += p[i].b;
        q.push(p[i].b);
    }
    ans = min(ans, p[k].a * res);
    for (int i = k + 1; i <= n; i++)
    {
        int op = q.top();
        ans = min(ans, p[i].a * (res - op + p[i].b));
        q.push(p[i].b);
        res += p[i].b;
        op = q.top();
        q.pop();
        res -= op;
    }
    cout << ans << endl;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    int test = 1;
    cin >> test;
    for (int i = 1; i <= test; i++)
    {
        solve();
    }
    return 0;
}