Hướng dẫn giải của Bedao Regular Contest 10 - ADMISSIONS
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tác giả:
Để dễ xử lý, ta sẽ có một mảng ~candidate~ chứa bốn loại giá trị khác nhau:
- ~math~ là số điểm Toán ứng viên đó đạt được
- ~info~ là số điểm Tin ứng viên đó đạt được
- ~ind~ là số thứ tự ban đầu của ứng viên đó
- ~total~ là tổng số điểm Toán và Tin mà ứng viên đó đạt được
Do đề bài ưu tiên điểm Toán đến điểm Tin và tới tổng điểm nên ta sẽ lần lượt thực hiện theo: Sắp xếp các ứng viên theo điểm Toán (lưu ý rằng với hai thí sinh có điểm Toán bằng nhau thì ta sẽ lấy thí sinh có số thứ tự ban đầu nhỏ hơn) rồi lấy ~x~ ứng viên thì danh sách này, trong lúc lấy ta sẽ vừa kiểm tra và đánh dấu xem thí sinh này đã được liệt vào danh sách hay chưa, lấy đủ ~x~ thí sinh thỏa mãn thì ta sẽ dừng. Đối với yêu cầu về điểm Tin và tổng điểm Toán-Tin, ta cũng sẽ làm tương tự.
Sau khi có mảng đáp án là số thứ tự ban đầu của các ứng viên, ta sẽ sắp xếp mảng đáp án theo thứ tự tăng dần và in ra.
Code mẫu
#include <bits/stdc++.h> #define int long long #define ii pair<int,int> #define nd second #define st first #define endl "\n" using namespace std; const int MAXN = 1005; int n, A, B, C, a[MAXN], b[MAXN]; bool vis[MAXN]; signed main(){ if (fopen("admissions.inp", "r")){ freopen("admissions.inp", "r", stdin); freopen("admissions.out", "w", stdout); } ios_base::sync_with_stdio(false); cin.tie(0); vector<ii> maths, cs, both; cin >> n >> A >> B >> C; for (int i = 1; i <= n; i++){ cin >> a[i]; maths.push_back({a[i], i}); } for (int i = 1; i <= n; i++){ cin >> b[i]; cs.push_back({b[i], i}); both.push_back({a[i] + b[i], i}); } sort (maths.begin(), maths.end(), [](ii x, ii y){ return (x.st != y.st ? x.st > y.st : x.nd < y.nd); }); sort (cs.begin(), cs.end(), [](ii x, ii y){ return (x.st != y.st ? x.st > y.st : x.nd < y.nd); }); sort (both.begin(), both.end(), [](ii x, ii y){ return (x.st != y.st ? x.st > y.st : x.nd < y.nd); }); for (int i = 0; i < A; i++) vis[maths[i].nd] = true; int cnt = 0; for (int i = 0; i < n; i++){ if (cnt == B) break; if (!vis[cs[i].nd]){ vis[cs[i].nd] = true; cnt++; } } cnt = 0; for (int i = 0; i < n; i++){ if (cnt == C) break; if (!vis[both[i].nd]){ vis[both[i].nd] = true; cnt++; } } for (int i = 1; i <= n; i++) if (vis[i]) cout << i << endl; }
Bình luận