本文使用 $\LaTeX$ 语法。若出现渲染失败或错误,请刷新页面并耐心等待刷新完成。

CF967B Watering System

题目

优先队列贪心+奇技淫巧

首先吐槽下,这个题的翻译是什么优(niu)秀(ma)东西!

  • 正常人能看懂的题意:输入$n,\ a,\ b$,再输入 $n$ 个数 $s$ ,$sum$ 为 $s$ 之和。删去除第一个数 $s1$ 外的数,使得 $a\times s1/sum \geqslant b$,求删数的最小个数。

    由于 $s1,\ a,\ b$ 不变,那么只要使 $sum$ 在删数最少的情况下最小即可。那么就删除当前最大的 $s$ 即为正解。

  • 但是,在此过程中,很多其他题解要不然就是忽略了 $a\times s1/sum \geqslant b$ 这一计算过程可能因为向下取整而出错的问题,要不是就像是第一篇大佬的一样,直接上double了。

    那么为什么不把这个式子直接改为 $a\times s1 \geqslant b\times sum$ 呢?这样就完美避免了上述问题。注意 $n \in [1,10^5]$ 且 $s \in [1,10^4]$,最坏情况下 $sum$ 与 $b$ 相乘时超过了int(我就因为这个WA了两次),所以应该使用long long

由于优先队列的小根堆默认从大到小排列,所以与贪心的要求完美切合。

  • 但是($\times 2$),默认的priority_queue是在臭名昭著大名鼎鼎的STL库中的,插入、弹出的最低复杂度都达到了 $\Theta(logN)$,不太能接受。

    这时我们就提到了一个叫做pb_ds的扩展库,俗称平板电视。它有很多模板,队列、平衡树等等等。我们现在就是要采用它的优先队列模板。平板电视提供了很多种时间复杂度的数据标记,由于我们的优先队列只需要poppush两大操作,所以我们就选复杂度稳定的rc_binomial_heap_tag(默认采用pairing_heap_tag,它的pop操作最坏情况可达 $\Theta(N)$),复杂度分别为 $\Theta(1)$ 和 $\Theta(logN)$。

平板电视的详情请参见这位大佬的日报

  • 具体地,在头文件引用时需要加入下面的代码:
    #include <ext/pb_ds/assoc_container.hpp>//基础扩展库
    #include <ext/pb_ds/priority_queue.hpp>//优先队列扩展库
    
  • 声明时,需要:

    __gnu_pbds::priority_queue<int,less<int>,__gnu_pbds::rc_binomial_heap_tag>pq;
    

    你没看错,甚至普通优先队列的vector<int>这一步骤都省了。(如果采用默认标记,甚至会更短)

  • 平板电视最好的一点,就是它把上面几个步骤写完之后的一切与std::priority_queue的操作一模一样。

    另外,此题输入量不是很大,不会还有人以为C++系的IO比C系的慢吧! 我们可以使用ios::sync_with_stdio(0);cin.tie(0);来使C++系IO变得飞快。当然输入量大的时候还是建议打快读。今年CSP-S的T1如果加上快读就能放过很多牛马暴力

最终代码及解析

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
#define int long long //防止#9爆int

int n,a,b;
int s1,s,sum,tot,p;
__gnu_pbds::priority_queue<int,less<int>,__gnu_pbds::rc_binomial_heap_tag>pq;

signed main(){
    ios::sync_with_stdio(0);cin.tie(0);
    cin>>n>>a>>b>>s1; //因为不能删掉第一个数,那么干脆不把它插进队列里。
    sum=s1; //但别忘了第一个数也在sum中。
    for(int i=1;i<n;i++){
        cin>>s;
        pq.push(s);
        sum+=s;
    }
    while(pq.size()){
        if(a*s1>=b*sum)break; //此处相乘会在#9爆int    
        tot++;
        sum-=pq.top();//最上层的便是最大的数
        pq.pop();
    }
    cout<<tot<<endl;
} 

The Only Thing That's Changed is EVERYTHING .