比赛链接：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;
}