CF2037D WA求调
查看原帖
CF2037D WA求调
223168
steve9572楼主2024/11/19 21:52

第2个点就WA

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
const int M = 2e5 + 10;
int find(int x, vector<pair<pair<int, int>, int>> &mfree)
{
    for (int i = 0; i < mfree.size(); i++)
    {
        if (x >= mfree[i].first.first && x <= mfree[i].first.second)
        {
            return i;
        }
    }
}
vector<int> mleft;
vector<int> mright;
vector<pair<pair<int, int>, int>> mfree;
vector<priority_queue<int>> vals;
int main()
{

    int T;
    cin >> T;
    for (int i = 0; i < T; i++)
    {
        int n, m, L;
        int l, r, pu, val;
        mleft.clear();
        mright.clear();
        mfree.clear();
        vals.clear();
        cin >> n >> m >> L;
        for (int j = 1; j <= n; j++)
        {
            cin >> l >> r;
            mleft.push_back(l);
            mright.push_back(r);
        }
        if(mright[n-1]<L)
            mfree.push_back(make_pair(make_pair(mright[n-1]+1,L),0));
        for (int j = n - 1; j >= 0; j--)
        {
            int ban = mright[j] - mleft[j] + 1;
            if (j >= 1)
            {
                mfree.push_back(make_pair(make_pair(mright[j - 1] + 1, mleft[j] - 1), ban));
            }
        }
        if (mleft[0] >= 2)
        {
            mfree.push_back(make_pair(make_pair(1, mleft[0] - 1), mright[0] - mleft[0]));
        }
        vals.resize(mfree.size());

        for (int j = 1; j <= m; j++)
        {
            cin >> pu >> val;
            int idx = find(pu, mfree);
            vals[idx].push(val);
        }
        int power = 0;
        int cnt = 0;
        bool flag = false;
        for (int j = mfree.size() - 1; j >= 0; j--)
        {
            while (power <= mfree[j].second && !vals[j].empty())
            {
                power += vals[j].top();
                cnt++;
                vals[j].pop();
            }
            while (power <= mfree[j].second)
            {
                int maxid = -1;
                int maxn = -1;
                for (int k = j + 1; k < mfree.size(); k++)
                {
                    if (!vals[k].empty() && maxn < vals[k].top())
                    {
                        maxn = vals[k].top();
                        maxid = k;
                    }
                }
                if (maxid == -1)
                {
                    flag = true;
                    break;
                }
                vals[maxid].pop();
                power += maxn;
                cnt++;
            }
            if (flag)
                break;
        }
        if (flag)
            cout << -1 << endl;
        if (!flag)
            cout << cnt << endl;
       
    }
}

2024/11/19 21:52
加载中...