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

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

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;
}