目录

---

A 天(贪心)

选择用小根堆维护。我们发现问题在于，当前\(j\)取了一个前面最小的\(i\)配对，但有可能后面有更优的\(k\)与\(i\)配对。

但是注意到\(a[k]-a[i]=a[k]-a[j]+a[j]-a[i]\)，我们可以让\(j\)选\(i\)，同时有机会让\(j\)撤销选\(i\)，即再在堆中加一个\(A[j]\)，但选取它不会增加次数（原本的\(A[j]\)当然还要有）。

而且选最小值的顺序是没有影响的，即\(j\)选了\(i\)而\(k\)选了个也比\(j\)小比\(i\)大的\(i'\)同样最优。

题解做法：

//185ms 2888kb#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#define gc() getchar()#define MAXIN 150000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)#define fir first#define sec second#define mp std::make_pair#define pr std::pair
        
         typedef long long LL;const int N=5e4+5;char IN[MAXIN],*SS=IN,*TT=IN;inline int read(){    int now=0;register char c=gc();    for(;!isdigit(c);c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now;}void Work(){    std::priority_queue
         
          
           ,std::greater
           
             > q;// while(!q.empty()) q.pop();//不清空要快很多... int n=read(); LL Ans=0; int cnt=0; for(int i=1; i<=n; ++i) { int ai=read(); if(q.empty()||q.top().fir>=ai) q.push(mp(ai,2)); else { Ans+=ai-q.top().fir, cnt+=q.top().sec; q.pop(); q.push(mp(ai,0)), q.push(mp(ai,2)); } } printf("%lld %d\n",Ans,cnt);}int main(){ for(int T=read(); T--; Work()); return 0;}
           
          
         
        
       
      
     
    

B 的(Prim)

首先我们可以二分答案。如何判断直径为\(x\)的球能否通过呢。

将上下边界也看做一个障碍点。任意两个障碍点如果距离不超过\(x\)则连边。当最后上下边界连通时，说明存在某些障碍点使得球不能通过。

这样复杂度为\(O(n^2\log Ans\ \alpha(n))\)。

我们可以利用Kruskal去做。将边全部从小到大排序，依次加入，当某一时刻上下边界连通时，则输出。

复杂度为\(O(n^2\log n^2+n^2\alpha(n))\)。（因为边数太多所以和上面差不多？）

这实际上是在求一棵\(n+2\)个点的最小生成树，直到上下边界连通。对于这样的图我们用Prim就可以\(O(n^2)\)了。

//9ms   612kb#include 
    
     #include 
     
      #include 
      
       #include 
       
        //#define gc() getchar()#define MAXIN 200000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)const int N=505;int read();bool vis[N];double dis[N];char IN[MAXIN],*SS=IN,*TT=IN;struct Point{    int x,y;    inline int Init() {return x=read(),y=read();}}p[N];inline int read(){    int now=0,f=1;register char c=gc();    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());    for(;isdigit(c);now=now*10+c-'0',c=gc());    return now*f;}inline double Dis(double x,double y){    return sqrt(x*x+y*y);}int main(){    int n=read(); double L=read();    for(int i=1; i<=n; ++i) dis[i]=p[i].Init();    dis[++n]=L; double ans=0;    for(int i=1; i<=n; ++i)    {        int now=n;        for(int j=1; j
       
      
     
    

C 碳(线段树)

记前缀和为\(pre\)，后缀和为\(suf\)。

一个显然的贪心是，从前往后枚举，找到一个\(pre<0\)的位置就把这个\(1\)删掉。然后对修改后的后缀和再这么求一遍。

事实上如果只考虑前缀（或者处理完前缀考虑后缀和），我们只需要找到一个\(\min\{pre_k\}/\min\{sum_k\}\)，记\(i/j\)为最小的前/后缀和的下标，那么\(|pre_i|\)就是前面总共要删的次数（\(|sum_j|\)为后面要删的次数）。

所以我们要求：\(\min\{pre_i\}-pre_{l-1}+\min\{sum_j\}-sum_{r+1}\)。

两个\(\min\)的和能否直接用线段树维护？

我们发现\(i<j\)时，两个\(\min\)互不影响；\(j\leq i\)时，答案可以表示为\(\min\{pre_k\}+sum_j(k<j)\)（怎么说...）。所以可以用线段树先找左边的最小的\(pre\)，然后用\(sum\)更新。

前/后缀和可能没有（如\(01\)），可以把初始前/后缀和\(>0\)的直接设为\(0\)；或者查的时候直接查\([l-1,r+1]\)。

//1329ms    11708kb#include 
    
     #include 
     
      #include 
      
       //#define gc() getchar()#define MAXIN 300000#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)const int N=2e5+5,INF=1e8;int pre[N],suf[N];char IN[MAXIN],*SS=IN,*TT=IN;struct Segment_Tree{    #define ls rt<<1    #define rs rt<<1|1    #define lson l,m,rt<<1    #define rson m+1,r,rt<<1|1    #define S N<<2    int ml[S],mr[S],mv[S];    #undef S    inline void Update(int rt)    {        ml[rt]=std::min(ml[ls],ml[rs]),        mr[rt]=std::min(mr[ls],mr[rs]),        mv[rt]=std::min(ml[ls]+mr[rs],std::min(mv[ls],mv[rs]));    }    void Build(int l,int r,int rt)    {        if(l==r)        {            ml[rt]=pre[l], mr[rt]=suf[l], mv[rt]=INF;            return;        }        int m=l+r>>1;        Build(lson), Build(rson);        Update(rt);    }    void Query(int l,int r,int rt,int L,int R,int &ans,int &minl)    {        if(L<=l && r<=R)        {//          if(minl==INF) minl=ml[rt], ans=mv[rt];            ans=std::min(ans,std::min(minl+mr[rt],mv[rt])), minl=std::min(minl,ml[rt]);            return;        }        int m=l+r>>1;        if(L<=m) Query(lson,L,R,ans,minl);        if(m