[Bài toán ở đây](https://marisaoj.com/problem/533)
Bài toán yêu cầu tìm số điểm lớn nhất có thể khi bấm các nút trong $q$ lượt bấm:
- Bấm nút $i$ sẽ được $s_i$ điểm.
- Nếu bấm nút đó lần đầu tiên thì sẽ được thêm $e_i$ điểm.
**Ý tưởng:**
- Ta sẽ bấm các nút có tổng $s_i + e_i$ là lớn nhất.
- Nút $i$ sau khi bấm lần đầu tiên thì $e_i = 0$.
- **Giả sử** sau khi bấm tất cả các nút ít nhất $1$ lần, ta chỉ việc Spam bấm nút có $s_i$ lớn nhất cho đến hết $q$ lượt.
Nếu nút này có $s_i + e_i$ (lúc này $e_i = 0$) lớn hơn các nút khác (Tính cả nút lúc chưa bấm lần nào) thì Spam nút đó mà không bấm các nút còn lại.
**Triển khai ý tưởng:**
- Khai báo mảng gồm $n$ phần tử là các nút, mỗi phần tử có $s_i$, $e_i$.
- Tìm giá trị $s_i$ lớn nhất.
- Thêm vào mảng phần tử có $s_i$ là giá trị lớn nhất tìm được và $e_i = 0$.
- $sort$ mảng theo tổng $s_i + e_i$, phần tử nào có $s_i + e_i$ bé hơn thì lên đầu.
- Với mỗi phần tử, bỏ bớt $1$ lượt bấm ($q -= 1$), cộng $s_i + e_i$ vào tổng điểm.
Nếu phần tử này có $e_i = 0$ thì thoát vòng lặp.
- Đáp án bài toán là tổng điểm cộng với $q$ lần giá trị $s_i$ lớn nhất.
**$\color{red}{C}\color{orange}{o}\color{yellow}{d}\color{green}{e}$** **$\color{blue}{C}\color{indigo}{+}\color{violet}{+}$**
~~(Bạn nào thích ngắn thì có thể ... #define int long long)~~
(Ở đây $first$ là $s_i$, $second$ là $e_i$)
```
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool custom(const pair<long long, long long>& x, const pair<long long, long long>& y){
return x.first + x.second > y.first + y.second;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, t = 0;
long long q, sv = 0;
cin>>n>>q;
vector<pair<long long, long long>> a(n);
for (int i = 0; i<n; ++i){
cin>>a[i].second>>a[i].first;
sv = max(sv, a[i].first);
}
a.push_back({sv, 0});
sort(a.begin(), a.end(), custom);
long long ans = 0;
while (q--){
ans += a[t].first + a[t].second;
if (not a[t].second) break;
t++;
}
cout<<ans + a[t].first * max(0LL, q);
return 0;
}
```
minhnhatha
Created at
1 likes