AcWing周赛62（C.三分）

迟到两周的总结（一直在补多校...）
过题数：3/3
排名：26/2341

C我写的是一个三分，调好久，他们写的二分好像也可以，还有其他做法，B我赛中用的线段树...实际上不用这么麻烦。

比赛链接：第 62 场周赛   - AcWing

A.三个元素（签到）

题意：给定一个长度为 $n$ 的数组 $r_1,r_2,…,r_n$。
请你找到其中的三个元素 $r_a,r_b,r_c$，使得 $r_a<r_b<r_c$ 成立。

思路：签到，暴力枚举，不过这里有个技巧是枚举中间的$b$，这样快一些，只需要枚举左右的$a,c$即可。

代码：

inline void Case_Test()
{
    cin>>n;
    for (int i=1;i<=n;i++)
        cin>>a[i];
    for (int i=2;i<n;i++)
    {
        int ans1 = -1, ans2 = -1;
        for (int l = 1;l<=n;l++)
            if (a[l]<a[i]) ans1 = l;
        for (int r = 1;r<=n;r++)
            if (a[r]>a[i]) ans2 = r;
        if (ans1!=-1 && ans2!=-1)
        {
            cout<<ans1<<" "<<i<<" "<<ans2<<endl;
            return;
        }
    }
    cout<<-1<<" "<<-1<<" "<<-1<<endl;
}

B.收集卡牌

题意：给你$n$张卡牌，一共有$m$种卡牌，对于按顺序的第$i(1\leq 1\leq n)$询问能够集齐一套进行兑换（1表示能够兑换）
例如：

Input:
3 11
2 3 1 2 2 2 3 2 2 3 1
Output:
00100000001

思路：赛中没有想法...直接用的线段树进行单点加法，区间查询最小值...实际上只需要想象成一个二维的，我用num数组来表示每一种卡牌有多少个（竖着），我用cnt数组来表示每一层，也就是每一套有多少个（横着）。
每次读入一个则对num[x]++，并且记录这一层多了一个，当这一层为m的时候说明集齐一套，进行下一套t++判断并且输出1,否则输出0。

代码：

int num[N],cnt[N];
inline void Case_Test()
{
    cin>>m>>n;
    int t = 1;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        num[x]++;
        cnt[num[x]]++;
        if (cnt[t]==m) 
        {
            cout<<1;
            t++;
        }
        else cout<<0;
    }
}

C.集合操作（三分）

题意：
给定一个由正整数（最初为空）组成的多重集 $S$。多重集表示可能存在重复元素的集合。

请你对该集合执行 $Q$ 次操作，操作分为两种：

增加操作，格式为 1 x，将一个正整数 $x$ 加入到集合 $S$ 中。数据保证，$x$ 不小于当前 $S$ 中的任何元素。
询问操作，格式为 2，找到一个当前 $S$ 的子集 $s$，要求 $max(s)−mean(s)$ 的值应尽可能大，输出 $max(s)−mean(s)$ 的最大可能值。$max(s)$ 表示 s 中最大元素的值，$mean(s)$ 表示 $s$ 中所有元素的平均值。

思路：每次加入，我想要$max(s)-mean(s)$最大，而每次的$x$又是不递减的，所以它就是当前最大的，然后在前面选择，我前缀和来优化，每次三分选择最大值与前面的答案进行比较并更新。

代码：

inline void Case_Test()
{
    cin>>q;
    double sum = 0, num = 0;
    while (q--)
    {
        int op;
        cin>>op;
        if (op==1)
        {
            cin>>x;
            a[++n] = x;
            pre[n] = a[n] + pre[n-1];
        }
        else
        {
            int l = 0, r = n-1;
            double ls,rs;
            if (l==r) {cout<<fixed<<setprecision(6)<<0.0<<endl;continue;}
            while (l<r)
            {
                int mid = (l+l+r)/3;
                int midmid = (r+r+l+2)/3;
                ls = (pre[mid]+a[n])/(double(mid+1));
                rs = (pre[midmid]+a[n])/(double(midmid+1));
                if (ls<rs) r = midmid-1;
                else l = mid+1;
            }
            ans = Max(ans, a[n]-Min(ls,rs));
            cout<<fixed<<setprecision(6)<<ans<<endl;
        }
    }
}