建议加强数据(
查看原帖
建议加强数据(
21091
sher_wu楼主2020/10/15 10:42

好像数据有点水

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;
}
2020/10/15 10:42
加载中...