题解 CF1203F1 【Complete the Projects (easy version)】
qcwlmqy
2019-08-14 20:51:23
### 思路
令当前$rating = r$,有$a_{1}, a_{ 2 }, b_{ 1 }, b_{ 2 }$
#### 对于$b_{i}$大于0的情况(洛谷的latex不会用~~)
#### 对于$b_{i}$小于0的情况
综上，对于$b_{i}\ge 0$按$a_{i}$排序
反之，按照$a_{i}+b_{i}$排序
### 代码
** 排序依据**
```cpp
bool cmp_a(const pii& a, const pii& b) {
return a.first < b.first;//b>0排序依据
}
bool cmp_b(const pii& a, const pii& b) {
return a.first + a.second > b.first + b.second;//b<0排序依据
}
```
** 预处理排序**
```cpp
for (int i = 1; i <= n; i++) {
cin >> x >> y;
if (y >= 0)a[++ml] = pii(x, y);
else b[++mr] = pii(x, y);
}
sort(a + 1, a + 1 + ml, cmp_a);
sort(b + 1, b + 1 + mr, cmp_b);
```
** 贪心**
```cpp
for (int i = 1; i <= ml; i++) {
if (a[i].first > r) {
printf("NO\n");
return 0;
}
r += a[i].second;
}
for (int i = 1; i <= mr; i++) {
if (b[i].first > r) {
printf("NO\n");
return 0;
}
r += b[i].second;
}
if (r >= 0)printf("YES\n");
else printf("NO\n");
```
** AC**
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef pair<int, int> pii;
const int maxn = 105;
pii a[maxn], b[maxn];
bool cmp_a(const pii& a, const pii& b) {
if (a.first == b.first) return a.second > b.second;
return a.first < b.first;
}
bool cmp_b(const pii& a, const pii& b) {
return a.first + a.second > b.first + b.second;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, r, x, y;
cin >> n >> r;
int ml = 0, mr = 0;
for (int i = 1; i <= n; i++) {
cin >> x >> y;
if (y >= 0)a[++ml] = pii(x, y);
else b[++mr] = pii(x, y);
}
sort(a + 1, a + 1 + ml, cmp_a);
sort(b + 1, b + 1 + mr, cmp_b);
for (int i = 1; i <= ml; i++) {
if (a[i].first > r) {
printf("NO\n");
return 0;
}
r += a[i].second;
}
for (int i = 1; i <= mr; i++) {
if (b[i].first > r) {
printf("NO\n");
return 0;
}
r += b[i].second;
}
if (r >= 0)printf("YES\n");
else printf("NO\n");
}
```