题目描述

n个不同正整数，求满足‘1-i个数字之间至少能选出m个数字使得他们的极差不超过k’的最小i是多少。

样例

输入 第一行n m k，然后是n个数字:
6 3 5
170 169 175 171 180 175
输出：
4

解法

并没有AC（14/20），只是看到目前还没人贡献解法，分享一下自己的思路。

由于选出的m个数一定在一个长度为k的区间内，所以我就事先准备好了所有可能的长度为k的区间，每输入一个数，就把包含它的所有区间的count++,如果count>=m，就说明这个区间已经凑齐m个数了，满足要求。
根据上述分析，每个数都会有k个包含它的区间（比如3会被[1 2 3]、[2 3 4]、[3 4 5]包含，这里k为3），所以复杂度为O（n*k），理论上可以过16个点，但其他地方可能还有bug。

C++ 代码

#include <iostream>
#include<vector>

using namespace std;
int n,m,k;
int minnum,maxnum;
vector<vector<bool>>r;
int num[100005];
int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&k);
    for(int i=0;i<n;i++){
        scanf("%d",&num[i]);
    }
    minnum = num[0];
    for(int i=0;i<n;i++){
        if(num[i]<=minnum)minnum=num[i];
        if(num[i]>=maxnum)maxnum = num[i];
    }
    for(int i=minnum;i<=maxnum-k;i++){
        vector<bool>tmp;
        r.push_back(tmp);
    }
    int len = maxnum-k-minnum;
    if(len<=0)
    {cout<<m;
    return 0;
        }//相差都不超过k
    for(int i=0;i<n;i++){
        for(int j = num[i]-k-minnum;j<=num[i]-minnum;j++){
            if((j>=0)&&(j<=len)){
                r[j].push_back(true);
                if(r[j].size()>=m){
                cout<< i+1;
                return 0 ;
                }
            }
        }
    }
    cout << "impossible" << endl;
    return 0;
}