专栏首页数据结构与算法BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序 贪心)

BZOJ2535: [Noi2010]Plane 航空管制2(拓扑排序 贪心)

题意

题目链接

Sol

非常妙的一道题。

首先不难想到拓扑排序,但是直接对原图按\(k\)从小到大拓扑排序是错的。因为当前的\(k\)大并不意味着后面的点\(k\)也大

但是在反图上按\(k\)从大到小拓扑排序就是对的。为什么呢?因为题目中给出的条件是下限, 而在反图上拓扑排序就相当于卡着下限做,因此一定是最优的

对于第二问,同样在反图上搞。对每个点分开做,贪心的策略是:如果有其他的飞机可以起飞则让他们起飞,直到没有飞机可以起飞,这时的时间就是答案

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
#define Pair pair<int, int>
#define MP(x, y) make_pair(x, y)
#define fi first
#define se second
using namespace std;
const int MAXN = 2e5 + 10;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int N, M, a[MAXN], inder[MAXN], tmp[MAXN], ans[MAXN];
vector<int> v[MAXN];
void Topsort() {
    priority_queue<Pair> q;
    for(int i = 1; i <= N; i++) 
        if(!inder[i]) q.push(MP(a[i], i));
    int tot = 0;
    while(!q.empty()) {
        int p = q.top().se; q.pop(); ans[++tot] = p;
        for(int i = 0, to; i < v[p].size(); i++) {
            to = v[p][i];
            inder[to]--;
            if(!inder[to]) q.push(MP(a[to], to));
        }
    }
    for(int i = tot; i >= 1; i--) printf("%d ", ans[i]); puts("");
}
int solve(int x) {
    memcpy(inder, tmp, sizeof(tmp));
    priority_queue<Pair> q;
    inder[x] = N;
    for(int i = 1; i <= N; i++) if(!inder[i]) q.push(MP(a[i], i));
    int tim = N; 
    for(int i = N; i; i--) {
        if(q.empty() || (q.top().fi < i)) return i;
        int p = q.top().se; q.pop(); 
        for(int i = 0, to; i < v[p].size(); i++) {
            to = v[p][i];
            inder[to]--;
            if(!inder[to]) q.push(MP(a[to], to));
        }
    }
    return tim;
}
int main() {
    N = read(); M = read();
    for(int i = 1; i <= N; i++) a[i] = read();
    for(int i = 1; i <= M; i++) {
        int x = read(), y = read();
        v[y].push_back(x); inder[x]++; tmp[x]++;
    }
    Topsort();
    for(int i = 1; i <= N; i++) printf("%d ", solve(i));
    return 0;
}
/*
10 10
4 4 3 6 9 9 10 7 10 7
2 9
3 5
6 7
1 5
7 9
10 2
3 8
8 6
3 10
8 5


*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)

    考虑K比较小的情况,可以直接暴力建SAM, 枚举w的子串算出现次数。询问用个 的vector记录一下每次在vector里二分就好。

    attack
  • BZOJ4010: [HNOI2015]菜肴制作(拓扑排序 贪心)

    attack
  • 洛谷P4723 【模板】线性递推(多项式取模 线性代数)

    attack
  • 洛谷P4723 【模板】线性递推(多项式取模 线性代数)

    attack
  • loj#6031. 「雅礼集训 2017 Day1」字符串(SAM 广义SAM 数据分治)

    考虑K比较小的情况,可以直接暴力建SAM, 枚举w的子串算出现次数。询问用个 的vector记录一下每次在vector里二分就好。

    attack
  • BZOJ4010: [HNOI2015]菜肴制作(拓扑排序 贪心)

    attack
  • HDU4576 Robot(概率)

    抄袭自https://www.cnblogs.com/Paul-Guderian/p/7624039.html

    attack
  • OpenCV图像处理专栏十 | 利用中值滤波进行去雾

    这是OpenCV图像处理专栏的第十篇文章,介绍一种利用中值滤波来实现去雾的算法。这个方法发表于国内的一篇论文,链接我放附录了。

    BBuf
  • C/C++感知机实现简单逻辑电路

    感知机算法是深度学习的基础。 感知机(Perceptron)定义 : 二类分类的线性分类模型,其输入为实例的特征向量,输出为实例的类别。 我们使用C/C++...

    英雄爱吃土豆片
  • 洛谷P3245 [HNOI2016]大数(莫队)

    两个位置\(l, r\)满足条件当且仅当\(S_l - S_r = 0\),也就是\(S_l = S_r\)

    attack

扫码关注云+社区

领取腾讯云代金券