得分：3 罚时：1:57:50 排名：114

第三题 $sum$ 开 $int$ 溢出害我交了 $8$ 次，真是服了我这个老六%%%

A. AcWing4500-三个元素

头一次见的有点复杂的A题，我的做法好复杂啊（排序+去重）。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=3005;
int a[MAXN],b[MAXN];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    memcpy(b,a,sizeof(a));
    sort(a+1,a+n+1);
    int len=unique(a+1,a+n+1)-a-1;
    if(len<3) printf("-1 -1 -1");
    else
    {
        for(int i=1;i<=n;++i)
        {
            if(b[i]==a[1])
            {
                printf("%d ",i);
                break;
            }
        }
        for(int i=1;i<=n;++i)
        {
            if(b[i]==a[2])
            {
                printf("%d ",i);
                break;
            }
        }
        for(int i=1;i<=n;++i)
        {
            if(b[i]==a[3])
            {
                printf("%d ",i);
                break;
            }
        }
    }
    return 0;
}

B. AcWing4501-收集卡牌

不要想太多，直接无脑线段树（单点修改+区间修改+区间查询最小值）。

#include<bits/stdc++.h>
using namespace std;

#define ls(p) p<<1
#define rs(p) p<<1|1
const int MAXN=1e5+5;
struct Segment_Tree
{
    int l,r,minn=0,tag=0;
}tree[MAXN<<2];
void push_up(int p)
{
    tree[p].minn=min(tree[ls(p)].minn,tree[rs(p)].minn);
}
void push_down(int p)
{
    int &t=tree[p].tag;
    if(t)
    {
        tree[ls(p)].minn-=t,tree[rs(p)].minn-=t;
        tree[ls(p)].tag+=t,tree[rs(p)].tag+=t;
        t=0;
    }
}
void build(int p,int l,int r)
{
    tree[p].l=l,tree[p].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(ls(p),l,mid);
    build(rs(p),mid+1,r);
}
void add(int p,int x,int t)
{
    if(tree[p].l==tree[p].r)
    {
        tree[p].minn+=t;
        return;
    }
    push_down(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(x<=mid) add(ls(p),x,t);
    else add(rs(p),x,t);
    push_up(p);
}
void update(int p,int l,int r,int t)
{
    if(l<=tree[p].l && tree[p].r<=r)
    {
        tree[p].minn-=t,tree[p].tag+=t;
        return;
    }
    push_down(p);
    int mid=(tree[p].l+tree[p].r)>>1;
    if(l<=mid) update(ls(p),l,r,t);
    if(r>mid) update(rs(p),l,r,t);
    push_up(p);
}
int query(int p,int l,int r)
{
    if(l<=tree[p].l && tree[p].r<=r) return tree[p].minn;
    push_down(p);
    int mid=(tree[p].l+tree[p].r)>>1,ret=MAXN;
    if(l<=mid) ret=min(ret,query(ls(p),l,r));
    if(r>mid) ret=min(ret,query(rs(p),l,r));
    return ret;
}
int main()
{
    int n,m;
    cin>>n>>m;
    build(1,1,n);
    int x;
    for(int i=1;i<=m;++i)
    {
        scanf("%d",&x);
        add(1,x,1);
        if(query(1,1,n))
        {
            putchar('1');
            update(1,1,n,1);
        }
        else putchar('0');
    }
    return 0;
}

C. AcWing4502-集合操作

贪心的想一下，肯定是优先选小的一堆+最大值。

然后对于小的数的数量其实是递增的，我的做法是用对顶堆来维护。

#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+5;
priority_queue< int,vector<int>,greater<int> >q1;
priority_queue<int>q2;
int main()
{
    int Q;
    cin>>Q;
    int opt,x,n=0,maxn;
    double sum=0;
    --Q;
    scanf("%d %d",&opt,&maxn);
    while(Q--)
    {
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d",&x);
            if(maxn<x) swap(maxn,x);
            if(!q2.empty() && x<q2.top()) q1.push(q2.top()),q2.push(x);
            else q1.push(x);
        }
        else
        {
            while(!q1.empty() && ((double)sum+maxn+q1.top())/(n+2)<((double)sum+maxn)/(n+1)) sum+=q1.top(),q2.push(q1.top()),++n,q1.pop();
            printf("%.6f\n",(double)maxn-((double)sum+maxn)/(n+1));
        }
    }   
    return 0;
}