CarryNotKarry

  • 首页
  • 语言学习
    • C++程序设计
    • 汇编语言
    • Python
  • 比赛总结
  • ACM-ICPC
    • 动态规划
    • 字符串
    • 搜索
    • 数学
    • 数据结构
    • 图论
    • 计算几何
    • 杂项
  • 分享
  • 上课内容
  • 其他
Carry
CUGBACMer/皇马球迷/C罗人迷
  1. 首页
  2. 比赛总结
  3. 正文

Educational Codeforces Round 131 (Rated for Div. 2)(D贪心/排序)

2022年7月14日 379点热度 0人点赞 0条评论

比赛链接:Dashboard - Educational Codeforces Round 131 (Rated for Div. 2) - Codeforces
上周的一场edu,一直没补,赛后1min过D,不然上大分:cold_sweat:。还是这时候给补上总结吧,D挺好的一个题,当时想错了,用优先队列确实好,前面几题随便写写,主要看D吧。

A. Grass Field

之前看错题,只需要统计1的个数,如果是0,4,其他对应的就是0,2,1。

B. Permutation

为了贪心,所以选择d=2,所以用类似于筛法,每次都乘以2,所以时间复杂度O(nlogn)

inline void Case_Test()
{
    cin>>n;
    cout<<2<<endl;
    for (int i=1;i<=n;i++) 
        vis[i] = 0;
    for (int i=1;i<=n;i++)
        for (int j=i;j<=n;j*=2)
        {
            if (!vis[j])
            {
                cout<<j<<" ";
                vis[j] = 1;
            }
        }
    cout<<endl;
}

C. Schedule Management(二分答案)

可以用二分答案x,每次对于每一个机器去判断a[i]是否大于x,如果大于的话那肯定需要拿出来分给其他机器;如果是小于的话,则可以从res接受,但是不大于x。

inline bool check(int x)
{
    int res = 0;
    for (int i=1;i<=n;i++)
    {
        if (a[i]>=x)
        {
            res += a[i]-x;
        }
        else
        {
            int t = (x-a[i])/2;
            res -= t;
        }
    }
    return res<=0;
}
inline void Case_Test()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) a[i] = 0;
    int ma = 0;
    for (int i=1;i<=m;i++)
    {
        cin>>x;
        a[x]++;
        ma = Max(ma,a[x]);
    }
    int l = 1, r = ma;
    while (l<r)
    {
        int mid = (l+r)>>1;
        if (check(mid)) r = mid;
        else l = mid+1;
    }
    cout<<l<<endl;
}

D. Permutation Restoration(排序/贪心,1900

题意

M有一个1...n的排列a,对于每一个i都有b_i = \left \lfloor \frac{i}{a_i} \right \rfloor,例如a=[2,1,4,3],那么b=[\left \lfloor \frac{1}{2} \right \rfloor,\left \lfloor \frac{2}{1} \right \rfloor,\left \lfloor \frac{3}{4} \right \rfloor,\left \lfloor \frac{4}{3} \right \rfloor]=[0,2,0,1]。现在a排列丢失,现在只知道b数组,求得到原来的一个a排列,输出任意即可。

思路

因为这里向下取整,所以肯定是一个范围,所以我设置了一个结构体,内部包含l,r,id,分别表示左右区间以及下标,这里分为两种情况:

  • 1)非0
    如果是不为0的话,我们令b_i=x,通过a_i=\left \lfloor \frac{i}{x} \right \rfloor 写出左右边界:(\frac{i}{x+1} \lt a_i \leq \frac{i}{x} ],注意这里是左开右闭并且是带小数的,如果要写成计算机代码的那么就是(\left \lfloor \frac{i}{x+1}\right \rfloor \lt a_i\leq \left \lfloor \frac{i}{x}\right \rfloor]。如果l,r表示能够选取的左右边界,那么l还需要+(因为左端点不可取)。
a[i].id = i;
a[i].l = i/(x+1)+1;
a[i].r = i/x;
  • 2)为0
    这里特殊一些,因为除以0就是无穷大,并且左边界就是i(不可取),所以可以左边界+1并且右边界设置n即可。
a[i].id = i;
a[i].l = i+1;
a[i].r = n;

重点来了:方法是用N个vector<PII>容器来存,v[i]的类型是PII,存的是右边界r以及下标id,该值存入v[a[i].l]中。

这样v[i]的存的值就是所有范围中,左区间为i的所有区间,至于为什么这么做,是因为我从1...n扫一遍的话,有些区间并没有符合条件,也就是左区间l比i还大,所以并不可取。

然后用一个优先队列pq每次取出当前队列中r最小的(因为这个时候选它肯定最优,可能先不选到后面就过了右区间过期了),每次对于for i = 1..n先将能够符合条件的加入队列,再从队列中选取top也就是r最小的,这时候给它赋值为i,不然先选大的,r较小还没填到就右区间过了。

    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;

    for (int i=1;i<=n;i++)
    {
        for (auto [r,id]:v[i])
        {
            if (vis[id])continue;
            pq.push({r,id});
        }
        auto [r,id] = pq.top();pq.pop();
        ans[id] = i;
    }

代码

struct node
{
    int id,l,r;
}a[N];
vector<PII> v[N];
inline void Case_Test()
{
    cin>>n;
    int l,r;
    int cnt1 = 0,cnt2 = 0;
    for (int i=1;i<=n;i++) v[i].clear();
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        vis[i] = 0;
        fa[i] = i;
        if (x==0)
        {
            a[i].id = i;
            a[i].l = i+1;
            a[i].r = n;
        }
        else
        {
            a[i].id = i;
            a[i].l = i/(x+1)+1;
            a[i].r = i/x;
        }
        v[a[i].l].push_back({a[i].r,i});
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    for (int i=1;i<=n;i++)
    {
        for (auto [r,id]:v[i])
        {
            if (vis[id])continue;
            pq.push({r,id});
        }
        auto [r,id] = pq.top();pq.pop();
        ans[id] = i;
    }

    for (int i=1;i<=n;i++)
        cout<<ans[i]<<" ";
    cout<<endl;
}
标签: CodeForces 排序 贪心
最后更新:2022年7月14日

Carry

来自于湖南长沙

点赞
< 上一篇
下一篇 >

文章评论

取消回复
标签
CodeForces 排序 贪心
文章目录
  • A. Grass Field
  • B. Permutation
  • C. Schedule Management(二分答案)
  • D. Permutation Restoration(排序/贪心,1900
    • 题意
    • 思路
    • 代码
其他文章

Carry爱三进制题解

【区间DP】POJ2955.Brackets

Codeforces Educational Round 122(Rated for Div.2)比赛总结 (rating+77)

汇编语言 实验四 子程序结构

汇编语言 实验三 循环结构和分支结构程序设计

C++程序设计

【基环树+思维】AcWing 1738.蹄球——每日一题2.6

AtCoder Beginner Contest 238比赛总结

【算法学习】线性基

【线性基】[BJWC2011]元素题解

From Carry
  • 在下不才,本博客也是为了记录自己的成长,并非成为非常专业的博客。
  • 如果有能够帮助你的地方是我最大的荣幸,一起加油吧!

ECNU-My love

THEME KRATOS MADE BY VTROIS