院里的天梯赛选拔搬了道–洛谷P7913 [CSP-S 2021] 廊桥分配

赛中懵掉想着是set做。。。

我们可以按照题意用优先队列进行模拟，用pair来存飞机离开时间和廊道编号，对于下一架飞机到达时，判断队列中飞机是否离开廊道，而廊道编号用set来存取

然后求出国内国际廊道的前缀和求解

#include <queue>
#include <algorithm>
#include <iostream>
#include <set>

using namespace std;

typedef pair<int, int> pii;
int n, m1, m2, x, y, agn[(int)1e5 + 9], agw[(int)1e5 + 9];

vector<pii> gn, gw;

int main()
{
    cin >> n >> m1 >> m2;
    for (int i = 1; i <= m1; ++i)
    {
        cin >> x >> y;
        gn.push_back({x, y});
    }
    for (int i = 1; i <= m2; ++i)
    {
        cin >> x >> y;
        gw.push_back({x, y});
    }

    sort(gn.begin(), gn.end(), [](pii a, pii b)
         { return a.first < b.first; });
    sort(gw.begin(), gw.end(), [](pii a, pii b)
         { return a.first < b.first; });

    priority_queue<pii, vector<pii>, greater<pii>> qgn, qgw;
    set<int> sgn, sgw;
    for (int i = 1; i <= n + 1; ++i)
    {
        sgn.insert(i);
        sgw.insert(i);
    }
    for (auto [a, b] : gn)
    {
        while (!qgn.empty() && qgn.top().first <= a)
        {
            sgn.insert(qgn.top().second);
            qgn.pop();
        }
        int t = *sgn.begin();
        if (t <= n)
        {
            sgn.erase(t);
            agn[t]+=1;
            pii tt = {b, t};
            qgn.push(tt);
        }
    }

    for (auto [a, b] : gw)
    {
        while (!qgw.empty() && qgw.top().first <= a)
        {
            sgw.insert(qgw.top().second);
            qgw.pop();
        }
        int t = *sgw.begin();
        if (t <= n)
        {
            sgw.erase(t);
            agw[t]+=1;
            pii tt = {b, t};
            qgw.push(tt);
        }
    }

    for(int i=1;i<=n;++i){
        agn[i]+=agn[i-1];
        agw[i]+=agw[i-1];
    }


    int ans=0;
    for(int i=0;i<=n;++i){
        ans=max(ans,agn[i]+agw[n-i]);
    }
    cout<<ans;
}

另一题是今晚的Codeforces Round #778 (Div. 1 + Div. 2, based on Technocup 2022 Final Round) C. Alice and the Cake

没想到今晚竟然记错时间错付了。。。。

一开始想的是用set来模拟合成数字，最后判断是否合成一个数字。但对于下面这组数据，可以发现贪心是无法完成任务的

6 1 1 1 1 1 1

泡了会破站想到维护两个优先队列，从正向进行。

首先求出各数之和放入一个优先队列中，然后原数据各个数放入另一个优先队列，对于每次操作前判断前者最大值是否大于等于后者，否则的话跳出操作返回false

然后再判断两者最大值是否相等，相等则均弹出，最后分解前者队列中的最大值。

#include <algorithm>
#include <iostream>
#include <queue>
#include <functional>

using namespace std;

long long tt, n, x, cnt;

int main()
{
    ios::sync_with_stdio(false);
    cin >> tt;
    for(int kkk=1;kkk<=tt;++kkk)
    {
        cin >> n;
        cnt = 0;
        priority_queue<long long, vector<long long>, less<long long>> q;
        for(int i=1;i<=n;++i)
        {
            cin >> x;
            q.push(x);
            cnt += x;
        }
        if (n == 1)
        {
            cout << "YES\n";
            continue;
        }

        function<int(long long)> fl = [&](long long a)
        {
            priority_queue<long long, vector<long long>, less<long long>> ori;
            ori.push(a);
            while ( !q.empty()&&ori.top() >= q.top() )
            {
                while (!q.empty()&&ori.top() == q.top() )
                {
                    ori.pop();
                    q.pop();
                }
                if (!ori.empty())
                {
                    long long t = ori.top();
                    ori.pop();
                    ori.push((t + 1) >> 1);
                    ori.push(t >> 1);
                }
            }
            return q.size();
        };
        int ok = fl(cnt);
        cout << (ok ? "NO\n" : "YES\n");
    }
    return 0;
}