【题目记录】——牛客练习赛87

痛定思痛。 2022-09-06 15:18 173阅读 0赞

### 文章目录 ###

*  A 中位数 思维
 *  B k小数查询 可持久化线段树

题目集地址 [牛客练习赛87][87]  
个人赛 制作出一题A

# A 中位数 思维 #

题目地址[A 中位数][A]  
思路：要使中位数最小，只需要每次选择数字的时候选择最大的两位即可，因为每操作一次就删除一个数，那么每次的中位数只需要是 (n-k+1)/2即可。当n-k等于1时属于特例，输出所有数的和。  
AC代码：

/* **Author:skj **Time: **Function: */
    #include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 2e5+5;
    int a[N];
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
        int t;
        scanf("%d",&t);
        while(t--)
        { 
            ll sum = 0;
            int n, k;
            scanf("%d%d",&n,&k);
            for(int i = 1;i <= n;i++)
            { 
                scanf("%d",a+i);
                sum += a[i];
            }
            if(n-k>1)
            { 
                sort(a+1,a+n+1);
                printf("%d\n",a[(n-k+1)/2]);
            }
            else
            { 
                printf("%lld\n",sum);
            }
        }
        return 0;
    }

# B k小数查询 可持久化线段树 #

题目地址[B k小数查询][B k]  
思路：由于 a 1 , a 2 , . . . , a n \{a\_1,a\_2,...,a\_n\} a1,a2,...,an是\{1,2,…,n\}的排列，所以x只出现一次。设x所在的位置为pos，令 l i l\_i li为\[i,pos−1\]中小于x的数的个数，r\[i\]为\[pos+1,i\]中小于x的个数。答案为  ∑ i = 1 p o s − 1 ∑ j = p o s + 1 n \[ l i + r j = k − 1 \] + ∑ i = 1 p o s − 1 \[ l i = = k \] + ∑ i = p o s + 1 \[ r i = = k \] + \[ k = = 1 \] \{\\sum\\limits\_\{i=1\}^\{pos-1\}\\sum\\limits\_\{j=pos+1\}^n\[l\_i+r\_j=k-1\]\}+\\sum\\limits\_\{i=1\}^\{pos-1\}\[l\_i==k\]+\\sum\\limits\_\{i=pos+1\}\[r\_i==k\]+\[k==1\] i=1∑pos−1j=pos\+1∑n\[li\+rj=k−1\]\+i=1∑pos−1\[li==k\]\+i=pos\+1∑\[ri==k\]\+\[k==1\]用一个桶来计数 r i r\_i ri，枚举 l i l\_i li即可。  
被题目给骗了，我以为是要用可持久化线段树。  
AC代码：

#include <bits/stdc++.h>
    #define ll long long
    #define INF 0x3f3f3f3f
    using namespace std;
    const int N = 2e5+5;
    int a[N];
    int l[N];
    int r[N],rn[N];
    int main()
    { 
    // freopen("in.txt","r",stdin);
    // freopen("out.txt","w",stdout);
    	int n, x, k;
    	scanf("%d%d%d",&n,&x,&k);
    	int pos = N;
    	for(int i = 1;i <= n;i++)
        { 
            scanf("%d",a+i);
            if(a[i]==x)
            { 
                pos = i;
            }
            if(i > pos)
            { 
                if(a[i] < x)
                { 
                    r[i] = r[i-1]+1;
                    rn[r[i]]++;
                }
                else
                { 
                    r[i] = r[i-1];
                    rn[r[i]]++;
                }
            }
        }
        ll ans = 0;
        for(int i = pos-1;i >= 1;i--)
        { 
            if(a[i] < x)
            { 
                l[i] = l[i+1]+1;
            }
            else
            { 
                l[i] = l[i+1];
            }
            if(l[i] == k-1)
            { 
                ans += (rn[0]+1);
            }
            else if(l[i] < k-1)
            { 
                ans += rn[k-1-l[i]];
            }
        }
        ans += rn[k-1];
    
        printf("%lld\n",ans);
    
        return 0;
    }

[87]: https://ac.nowcoder.com/acm/contest/11177
[A]: https://ac.nowcoder.com/acm/contest/11177/A
[B k]: https://ac.nowcoder.com/acm/contest/11177/B