HDU 5701 中位数计数（数论）

曾经终败给现在 2022-09-23 12:49 135阅读 0赞

题目链接：http://acm.hdu.edu.cn/viewcode.php?rid=17615323

位数定义为所有值从小到大排序后排在正中间的那个数，如果值有偶数个，通常取最中间的两个数值的平均数作为中位数。

现在有n个数，每个数都是独一无二的，求出每个数在多少个包含其的区间中是中位数。

题目大意：给你1-n一共n个数，让你枚举所有区间，找出每个区间的中位数，最后输出每个数一共当了多少次中位数

解题思路:  
最暴力的想法肯定是枚举所有区间，通过排序找出所有区间的中位数，时间复杂度n^3log(n)。  
队友提醒了一下可以不用排序，直接用线段树找第k大，复杂度n^2\*log(n)，依旧会超时。  
关键耗时是在枚举区间上，其实可以根据中位数的性质更优雅的枚举所有区间。  
假设Trb和Trs分别是数i右边比i大的和比i小的数的个数，Tlb和Tls分别是数i左边比数i大的和比i小的个数，假设i在这个区间中为中位数，则  
Trb-Trs=Tls-Tlb；  
因为Trb+Tlb=Trs+Tls（比i大的数等于比i小的数）

所以我们可以先向右边扩展，找出所有Trb-Trs值并用数组记录，再向左边扩展，找出所有Tls-Tlb，如果数组中有对应的值就在答案中相加，注意相减为0的情况要特殊处理一下。

AC 代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    int a[8005];
    
    int b[8005*2];
    
    int main()
    {
        int n;
    
        while(RI(n)!=EOF)
        {
            for(int i=0;i<n;i++)
            RI(a[i]);
            for(int i=0;i<n;i++)
            {
                memset(b,0,sizeof(b));
                int ans=0;
                int sta=8000;
    
                int ex=0;
                for(int j=i+1;j<n;j++)
                {
    
                    if(a[j]>a[i]) ex++;
                    else ex--;
                    b[sta+ex]++;
                }
                ex=0;
    
                for(int j=i-1;j>=0;j--)
                {
    
                    if(a[j]>a[i]) ex++;
                    else ex--;
                    ans+=b[sta-ex];
                    if(ex==0) ans++;
                }
    
                ans+=(b[sta]+1);
                if(i!=n-1) printf("%d ",ans);
                else printf("%d",ans);
            }
            printf("\n");
    
    
        }
    
    
    
        return 0;
    }