好像数据有点水
5 18
1 8
2 8
4 7
6 3
7 1
这组答案是3,但是我的输出是2。但是我的假代码能AK。
以下为假代码
#include <bits/stdc++.h>
#define For(i, l, r) for (register int i = l, _r = r; i <= _r; ++i)
#define Ford(i, l, r) for (register int i = r, _l = l; i >= _l; --i)
using namespace std;
typedef long long ll;
#define pii pair<ll, int>
#define mk make_pair
#define db double
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
const int N = 1e5 + 20;
const int INF = 1e9 + 7;
ll n, m, ans, pre;
ll a[N];
priority_queue<pii, vector<pii>, greater<pii>> q1;
priority_queue<int> q2;
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9'){if (ch == '-')f = -1;ch = getchar();}
while (ch >= '0' && ch <= '9'){x = (x << 3) + (x << 1) + ch - '0';ch = getchar();}
return x * f;
}
signed main()
{
n = read(), m = read();
For(i, 1, n) { q1.push({read(), read()}); }
For(i, 1, n)
{
pii now = q1.top();
q1.pop();
if(now.first - pre + now.second <= m)
{
m -= now.first - pre + now.second;
pre = now.first;
ans++;
q2.push(now.second);
}
else if(!q2.empty() && now.first - pre + now.second <= q2.top())
{
m -= now.first - pre + now.second - q2.top();
q2.pop();
pre = now.first;
q2.push(now.second);
}
}
cout << ans << endl;
}