社区讨论

求助!95分,#9测试的爆WA

P7913[CSP-S 2021] 廊桥分配参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo8e5k10
此快照首次捕获于
2023/10/27 17:08
2 年前
此快照最后确认于
2023/10/27 17:08
2 年前
查看原帖

Code in C++

CPP
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100005

#define dMAX(a, b) ((a) > (b) ? (a) : (b))
#define dMIN(a, b) ((a) < (b) ? (a) : (b))

struct Airline // 航班结构体
{
    int ari; // 到达时间
    int lea; // 离开时间
    bool inline operator>(const Airline &) const;
    bool inline operator<(const Airline &) const;
};

struct CnvBridge // 廊桥结构体
{
    int due; // 当前停靠飞机离开时间
    int cnt; // 停靠的飞机总数
    CnvBridge(const int &a = 0, const int &b = 0) : due(a), cnt(b) {}
};

int n, m1, m2;                      // 廊桥个数,国内航班数,国际航班数
Airline dom_f[MAXN], for_f[MAXN];   // 国内航班,国际航班
CnvBridge dom_b[MAXN], for_b[MAXN]; // 国内廊桥,国际廊桥
int dom_sum[MAXN], for_sum[MAXN];   // 前缀和

void input();
void solve();
int read();

int main()
{
    freopen("P7913_9.in", "r", stdin);
    input();
    solve();

    // 前缀和处理
    dom_sum[0] = 0, for_sum[0] = 0; // 不用0下标
    for (int i = 1; i <= m1; i++)
        dom_sum[i] = dom_sum[i - 1] + dom_b[i - 1].cnt;
    for (int i = 1; i <= m2; i++)
        for_sum[i] = for_sum[i - 1] + for_b[i - 1].cnt;

    // for (int i = 0; i <= m1; i++)
    //     cout << dom_sum[i] << ' ';
    // cout << endl;
    // for (int i = 0; i <= m2; i++)
    //     cout << for_sum[i] << ' ';
    // cout << endl;

    int ans = 0;
    for (int i = 0; i <= n; i++)
        ans = dMAX(ans, dom_sum[i] + for_sum[n - i]);
    cout << ans << endl;

    return 0;
}

void solve()
{
    sort(dom_f, dom_f + m1); // 对国内航班到达时间排序
    sort(for_f, for_f + m2); // 对国际航班到达时间排序

    for (int i = 0; i < m1; i++) // 模拟国内航班的到达情况
        for (int j = 0;; j++)    // 枚举国内廊桥,若数据合法,则不会数组越界
        {
            CnvBridge &cb = dom_b[j];
            if (cb.due < dom_f[i].ari) // 如果之前停靠在此廊桥的飞机已经离开
            {
                cb.due = dom_f[i].lea, cb.cnt++; // 更新当前停靠飞机离开时间和停靠飞机总数
                break;
            }
        }

    for (int i = 0; i < m2; i++) // 国际,逻辑同上
        for (int j = 0;; j++)
        {
            CnvBridge &cb = for_b[j];
            if (cb.due < for_f[i].ari)
            {
                cb.due = for_f[i].lea, cb.cnt++;
                break;
            }
        }

    // /* Debug - View dom_b[] & for_b[] */
    // cout << "国内:" << endl;
    // for (int i = 0; i < m1; i++)
    //     cout << "  " << i << ": " << dom_b[i].cnt << endl;
    // cout << "国际:" << endl;
    // for (int i = 0; i < m2; i++)
    //     cout << "  " << i << ": " << for_b[i].cnt << endl;
}

void input()
{
    n = read(), m1 = read(), m2 = read();
    for (int i = 0; i < m1; i++)
        dom_f[i].ari = read(), dom_f[i].lea = read();
    for (int i = 0; i < m2; i++)
        for_f[i].ari = read(), for_f[i].lea = read();
}

bool inline Airline::operator>(const Airline &a) const
{
    return this->ari > a.ari;
}

bool inline Airline::operator<(const Airline &a) const
{
    return this->ari < a.ari;
}

inline int read()
{
    int f = 1, r = 0;
    char c = getchar();
    while (!isdigit(c))
        f ^= c == '-', c = getchar();
    while (isdigit(c))
        r = (r << 1) + (r << 3) + (c & 15), c = getchar();
    return f ? r : -r;
}

回复

1 条回复,欢迎继续交流。

正在加载回复...