Codeforces Round #647 (Div. 2) - Thanks, Algo Muse! D. Johnny and Contribution (贪心,模拟)
阅读原文时间:2023年07月08日阅读:2

  • 题意:有\(n\)个点,\(m\)条边,现在要给这些点赋值,,每次只能赋给某一点的四周(所连边)的最小没出现过的值.如果不能按照所给的数赋值,输出\(-1\),否则输出赋值顺序.

  • 题解:我们用\(pair\)记录最后一行所给的数和位置,不难想,每次肯定是赋最小的数,所以我们对其排序,然后遍历取位置,看这个位置周围能赋的值是否满足条件即可.

  • 代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    #include <stack>
    #include <queue>
    #include <vector>
    #include <map>
    #include <set>
    #include <unordered_set>
    #include <unordered_map>
    #define ll long long
    #define fi first
    #define se second
    #define pb push_back
    #define me memset
    const int N = 1e6 + 10;
    const int mod = 1e9 + 7;
    const int INF = 0x3f3f3f3f;
    using namespace std;
    typedef pair<int,int> PII;
    typedef pair<ll,ll> PLL;
    
    int n,m;
    int a,b;
    int num[N];
    vector<PII> mp;
    vector<int> v[N];
    vector<int> ans;
    
    int check(int pos){
        set<int> tmp;
        for(auto w:v[pos]){
            tmp.insert(num[w]);
        }
        num[pos]=1;
        while(tmp.count(num[pos]))
            num[pos]++;
        return num[pos];
    }
    
    int main() {
        ios::sync_with_stdio(false);cin.tie(0);
        cin>>n>>m;
        for(int i=1;i<=m;++i){
            cin>>a>>b;
            v[a].pb(b);
            v[b].pb(a);
        }
        for(int i=1;i<=n;++i){
            int x;
            cin>>x;
            mp.pb({x,i});
        }
        sort(mp.begin(),mp.end());
        for(auto w:mp){
            if(check(w.se)!=w.fi){
                puts("-1");
                return 0;
            }
            else ans.pb(w.se);
        }
        for(auto w:ans) printf("%d ",w);
    return 0;
    }