思路正确但是wa了, 求调
查看原帖
思路正确但是wa了, 求调
1072752
Kiraism楼主2024/11/24 00:18
#include <bits/stdc++.h>
#define int long long
#define IOS  {std::ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);}//关流
#define CLEAR(a) {memset(a, 0, sizeof(a));}
#define undirectedEdge(u, v, w) {e[u].push_back(edge(u, v, w)); e[v].push_back(edge(v, u, w));}
using namespace std;//上面的都别动
#define endl '\n'//无法刷新输出缓存区
const int INF = 0x3f3f3f3f3f3f3f3f;
const int inf = 0x3f3f3f3f;
const int MAXN = 2e6 + 10;
const int maxn = 2e5 + 10;
priority_queue<int> q;
//d[i]表示第i个障碍的长度, l[i]表示第i个障碍的左端点
int d[maxn], l[maxn];
//a[i]存的是第 i-1 到 i 个障碍中的所有药水
vector<int> a[maxn];

void solve(){
    int n, m, L, k = 1;
    cin>>n>>m>>L;
    //清空
    for(int i = 0; i <= n; ++ i)
    {
        a[i].clear();
        d[i] = 0;
        l[i] = 0;
    }
    while(!q.empty ())
    {
        q.pop ();
    }
    
    for(int i = 1; i <= n; ++ i)
    {
        int r;
        cin>>l[i]>>r;
        d[i] = r - l[i] + 1;
    }

    for(int i = 1; i <= m; ++ i)
    {
        int len, index, buf;
        cin>>len>>buf;
        index = (lower_bound(l + 1, l + n + 1, len) - l);
        a[index].push_back (buf);
    }

    int ans = 0;

    for(int i = 1; i <= n; ++ i)
    {
        for(auto e:a[i])
            q.push (e);

        while(k <= d[i] && !q.empty ())
        {
            k += q.top ();
            q.pop ();
            ans ++;
        }
        if(q.empty() && k <= d[i])
        {
            cout<<-1<<endl;
            return;
        }
    }
    cout<<ans<<endl;
}

signed main(){
    IOS;
    int t = 1;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

2024/11/24 00:18
加载中...