巨人国军训选人问题

客官°小女子只卖身不卖艺 2023-02-23 05:28 33阅读 0赞

Description  
（本题的描述和以前《军训选人问题》几乎一模一样，根本的区别就是数据范围扩大了，原来的方法应该不合适了，请另外思考解决问题的算法！！！）很多学校在每年的九月份新学期开学时对新生需要进行军训，巨人国也不例外，今年也开始军训了，第一天，总教官把所有新生都召集在一个很大的操场上，从1开始依次编号，他要从中选一部分身高符合要求的人参加护旗方队，为了便于管理，他决定符合要求的学生的编号是连续的，他现在想尽可能多选，因为训练中可能会有很多学生由于种种原因而退出，总教官的要求是被选中的同学中任何两个的身高差有限制，不能超过规定的要求。亲爱的同学们，如果你们想帮总教官，那么你就帮他写个程序，计算一下符合要求的学生最多到底是多少？假定学生人数为n（1<=n<=200000）,身高h（1<=h<= 1000000），身高的单位是米而且是整数。

Input  
本问题有多组测试数据，对于每组测试数据，输入有两行，第一行是学生的人数n和身高的最大允许差，另一行是所有学生的身高。

Output  
输出也有两行，第一行的格式是：“From=XX，To=XX”，第二行的格式是：“MaxLen=XX”。本问题有多组测试数据。如果有多组符合要求的解，那么输出所有符合条件的解中起始编号最小的解。

Sample Input

11 15
    165 180 187 160 170 180 153 175 190 178 163

Sample Output

From=8,To=10
    MaxLen=3

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int maxn=200010;
    int s[maxn];
    int f[maxn][20],g[maxn][20];
    int n;
    void ST_prework()
    {
        
        for (int i = 1; i <= n; i++)
        {
        
            g[i][0] = s[i];
            f[i][0] = s[i];
        }
        for (int i = 1, imax = log2(n); i <= imax; i++)
        {
        
            for (int j = 1; j + (1 << i) - 1 <= n; j++)
            {
        
                g[j][i] = min(g[j][i - 1], g[j + (1 << i - 1)][i - 1]);
                f[j][i] = max(f[j][i - 1], f[j + (1 << i - 1)][i - 1]);
            }
        }
    }
    
    int ST_query(int l, int r)
    {
        
        int k = log2(r - l + 1);
        return max(f[l][k], f[r - (1 << k) + 1][k])-min(g[l][k], g[r - (1 << k) + 1][k]);
    }
    int main()
    {
        
        int v;
        while(~scanf("%d%d",&n,&v))
        {
        
            for(int i=1;i<=n;i++)scanf("%d",&s[i]);
            ST_prework();
            int l=1,r=1,cnt=1;
            int i=1,j=1;
            while(i<=n&&j<=n)
            {
        
                if(ST_query(i,j)<=v)
                {
        
                    if(j-i+1>cnt)
                    {
        
                        l=i;
                        r=j;
                        cnt=r-l+1;
                    }
                    j++;
                }
                else i++;
            }
            printf("From=%d,To=%d\nMaxLen=%d\n",l,r,cnt);
        }
        return 0;
    }