大模拟全错,只求理清思路骗一点分
查看原帖
大模拟全错,只求理清思路骗一点分
486158
Aludy楼主2021/10/26 16:39

大佬帮忙找个错吧

我真的是无语了,初赛没过也就算了,这第一题都想不明白

来个高人指点我这个蒟蒻一下吧

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>

using namespace std;

const int M = 1e5 + 10;
int n, m1, m2;
int b1[M], b2[M];

struct node{
    int num, s, e; // num表示如果可以会停在第几个廊桥
}temp[M];

bool cmp(node i, node j) {
    return i.s < j.s;
}

struct tmp{
    bool operator() (node a, node b) {
        return a.e > b.e; // 小顶堆
    }
};

void debug(int k[]) {
    for (int i = 0;i <= 50;i ++)
        cout << k[i] << ' ';
    cout << endl;
}

void solve(int m, int b[]) {
    memset(temp, 0, sizeof temp);

    for (int i = 1;i <= m;i ++) {
        cin >> temp[i].s >> temp[i].e;
    }
    sort(temp + 1, temp + m + 1, cmp);
    
    priority_queue<node, vector<node>, tmp> q;

    temp[1].num = 1;
    q.push(temp[1]);
    int idx = 2;
    int mx = 1;
    while (idx <= m) { // 模拟飞机进出机场的情况
        if (q.top().e < temp[idx].s) {
            temp[idx].num = q.top().num; 
            // 若有飞机可以走了,就停在要走的廊桥中
            q.pop();
            q.push(temp[idx]);
        }
        else {
            mx ++;
            temp[idx].num = mx;
            q.push(temp[idx]); 
            // 没有空位,另外开拓廊桥
        }
        idx ++;
    }

    for (int i = 1;i <= n + 1;i ++) {
        b[i] = 0;
    }
    for (int i = 1;i <= m;i ++) {
        b[temp[i].num] ++;
    }

    for (int i = 1;i <= n;i ++) {
        b[i] += b[i - 1];
        // 前缀和求一种机场里若有 i 个廊桥就会有 b[i] 个飞机可以停在廊桥里
    }
    
}

int main() {
    cin >> n >> m1 >> m2;

    solve(m1, b1);
    solve(m2, b2);

    // debug(b1);debug(b2);

    int i = 0, ans = 0;
    while (n - i > 0) {
        ans = max(ans, b1[i] + b2[n - i]); // 取最大值
        i ++;
    }

    cout << ans << endl;

    return 0;
}

想了半天了,虽然能过1,2样例,但数据大的样例3都过不去,数据太大也不好手算模拟。

救救孩子吧!!!!

2021/10/26 16:39
加载中...