构造——cf1214E

深藏阁楼爱情的钟 2023-10-11 09:04 30阅读 0赞

首先定义三元组（2\*i-1,2\*i,d），将n个三元组按d降序排列，然后取每个三元组的2\*i-1连在一起，构成一条长为n-1的链

然后降序枚举每个三元组，把对应的2\*i在链上合法的位置接上， 能保证一定有解

#include<bits/stdc++.h>
    using namespace std;
    #define N 200005
    struct Node{
        int a,b,d;}p[N];
    int cmp(Node a,Node b){
        return a.d>b.d;}
    
    int n;
    vector<pair<int,int> >ans;
    int id[N],cnt;
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            p[i].a=2*i-1,p[i].b=2*i;
            cin>>p[i].d;
        }
        sort(p+1,p+1+n,cmp);
        
        for(int i=1;i<n;i++){
            int u=p[i].a,v=p[i+1].a;
            ans.push_back(make_pair(u,v));
            id[i]=u;    
        }
        id[n]=p[n].a;
        cnt=n;
        
        for(int i=1;i<=n;i++){
            int len=cnt-i;//当前最长的长度
            if(p[i].d==len+1){
        //需要接在末尾 
                int u=id[cnt],v=p[i].b;
                ans.push_back(make_pair(u,v));
                id[++cnt]=v; 
            }
            else {
        //不用接在末尾 
                int u=id[i+p[i].d-1],v=p[i].b;
                ans.push_back(make_pair(u,v)); 
            }
        }
        
        for(int i=0;i<ans.size();i++)
            cout<<ans[i].first<<" "<<ans[i].second<<'\n';
    }

转载于:https://www.cnblogs.com/zsben991126/p/11468918.html

发表评论取消回复

表情：

评论列表（有 0 条评论，30人围观）

还没有评论，来说两句吧...

相关阅读

相关 CF1214D

CF1214D 题意： > 给你一个 $ n \\times m $ 的矩阵，求最少用多少个障碍，将 $ (1,1) $ 到 $ (n,m) $ 的路径堵死...

た入场券/ 2024年04月20日 10:34/ 0 赞/ 97 阅读

相关 CF1214C

CF1214C 题意： > 给你一个括号序列，问你时候能仅移动相邻的两个元素，使括号序列合法。解法： > 可以先考虑普通括号序列怎么做 > 这...

亦凉/ 2024年04月20日 10:33/ 0 赞/ 92 阅读

相关 CF1214B

CF1214B 解法： > 暴力枚举，时间复杂度 $ O(n) $ CODE: include<iostream> include<cstd...

不念不忘少年蓝@/ 2024年04月20日 10:33/ 0 赞/ 99 阅读

相关 CF1214A

CF1214A 题意： > 有n个卢布，要换成美元和欧元，使手上剩余的卢布最少。一美元价值d卢布，一欧元价值e卢布。解法： > 可以看成只有两个没...

「爱情、让人受尽委屈。」/ 2024年04月20日 10:32/ 0 赞/ 93 阅读

相关【构造】CF1761 E

[Problem - 1761E - Codeforces][] 题意： ![0622cda9a5a44fcfbb3df51c5babd8bc.png][] 思路：

缺乏、安全感/ 2024年03月23日 22:53/ 0 赞/ 94 阅读

相关【构造】CF1734 E

[Problem - 1734E - Codeforces][] 题意： ![434e61d374814555abe1a965962475f0.png][] 思路： !

超、凢脫俗/ 2024年03月23日 22:45/ 0 赞/ 75 阅读

相关【构造+拓扑排序】CF1385E

[Problem - 1385E - Codeforces][] 题意： ![e5bb03d5f2804bc7871a58b507e1dcca.png][] ![4249

r囧r小猫/ 2024年03月17日 11:37/ 0 赞/ 65 阅读

相关构造——cf1214E

首先定义三元组（2\i-1,2\i,d），将n个三元组按d降序排列，然后取每个三元组的2\i-1连在一起，构成一条长为n-1的链然后降序枚举每个三元组，把对应的2\i在链上

深藏阁楼爱情的钟/ 2023年10月11日 09:04/ 0 赞/ 31 阅读

相关网格图必经点+dfs——cf1214D

先正着走一次把所有可行路径标记出来，然后倒着走两条路径，一条是能向下就向下的路径，另一条能向右就向右。如果这两条路径相交，那么(1,1)-(n,m)路径上比有个必经点，把这

不念不忘少年蓝@/ 2023年10月11日 07:49/ 0 赞/ 33 阅读

相关 cf 1009E

如何看待某cf2000分选手不会一道tag1900的题？难。考虑每段距离的贡献， a\[i\]出现在位置j上，当且仅当j-i休息，并且中间的都不是休息的。

曾经终败给现在/ 2021年10月25日 12:56/ 0 赞/ 286 阅读