【题解】 ABC 461

A 题

很简单的一道题目，判断两个数的大小关系即可。

时间复杂度O(1)，空间复杂度O(1)。

#pragma GCC optimize("O3")#include<bits/stdc++.h>
using namespace std;#define endl "\n"int main(){ios::sync_with_stdio(0);cin.tie(0);//freopen("test.in", "r", stdin);//freopen("test.out", "w", stdout);int a, d; cin >> a >> d;if(a <= d) cout << "Yes" << endl;else cout << "No" << endl;return 0;
}

赛时解决链接

B 题

也相对简单，判断每一组关系互相匹配否即可。

#pragma GCC optimize("O3")#include<bits/stdc++.h>
using namespace std;#define endl "\n"int main(){ios::sync_with_stdio(0);cin.tie(0);//freopen("test.in", "r", stdin);//freopen("test.out", "w", stdout);int n; cin >> n;vector<int> a(n), b(n);for(int i = 0;i < n;i ++){cin >> a[i];}for(int i = 0;i < n;i ++){cin >> b[i];}for(int i = 0;i < n;i ++){if(b[a[i] - 1] != i + 1){cout << "No" << endl;return 0;}}cout << "Yes" << endl;return 0;
}

赛时通过链接

C 题

有一定难度，是反悔贪心，代码如下

#pragma GCC optimize("O3")#include<bits/stdc++.h>
using namespace std;#define endl "\n"
#define int long longconst int maxn = 200010;
struct Variety
{ int c, v; 
} var[maxn];bool cmp(Variety a, Variety b)
{return a.v > b.v;
}signed main(){ios::sync_with_stdio(0);cin.tie(0);//freopen("test.in", "r", stdin);//freopen("test.out", "w", stdout);int n, k, m; cin >> n >> k >> m;for(int i = 1;i <= n;i ++){cin >> var[i].c >> var[i].v;}sort(var + 1, var + 1 + n, cmp);unordered_map<int, int> cnt;priority_queue<int, vector<int>, greater<int>> pq;int tot = 0, type = 0;for(int i = 1;i <= k;i ++){if(cnt[var[i].c] == 0) type ++;else pq.push(var[i].v);cnt[var[i].c] ++, tot += var[i].v;}if(type >= m){cout << tot << endl;return 0;}for(int i = k + 1;i <= n;i ++){if(cnt[var[i].c] == 0 && !pq.empty()){int small = pq.top(); pq.pop();tot += var[i].v - small;cnt[var[i].c] ++, type ++;if(type >= m) break;}}cout << tot << endl;return 0;
}

赛时通过链接

D 题

好了11点半了，主播该去睡觉了，明天早上起来更。