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

比赛链接

AtCoder Beginner Contest 376

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);elsetmp = 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);elsetmp = 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;}elseidx--;}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;
}