思路

  • 我们可以把所有人的不同等级的分数用结构体存起来
    然后根据分数大小及进行排序

  • 根据双指针的做法来模拟
    这里注意:
    如果j遍历到等级A的分数,此前没有他的分数时,需要cnta++(cnta表示当前A等人数)
    如果j遍历到不是等级A的分数,此前有且仅有他的等级A的分数,需要cnta--
    如果i遍历到等级A的分数,此前没有他的分数时,需要cnta--
    如果i遍历到不是等级A的分数,此前有且仅有他的等级A的分数,需要cnta++

代码

// Problem: 内卷
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/9983/B
// Memory Limit: 524288 MB
// Time Limit: 6000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp(aa,bb) make_pair(aa,bb)
#define _for(i,b) for(int i=(0);i<(b);i++)
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,b,a) for(int i=(b);i>=(a);i--)
#define mst(abc,bca) memset(abc,bca,sizeof abc)
#define X first
#define Y second
#define lowbit(a) (a&(-a))
#define debug(a) cout<<#a<<":"<<a<<"\n"
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
typedef long double ld;
const int N=100010;
const int INF=0x3f3f3f3f;
const int mod=1e9+7;
const double eps=1e-6;
const double PI=acos(-1.0);

struct node{
    int score,id;
    bool st;//判断是不是A的分数
};

int n,k,ans=INF;
vector<node> g;
int cnt[N];
bool vis[N];

bool cmp(node a,node b){
    return a.score>b.score;
}

void solve(){
    cin>>n>>k;
    rep(i,1,n){
        int a,b,c,d,e;cin>>a>>b>>c>>d>>e;
        g.pb({a,i,1});
        g.pb({b,i,0});
        g.pb({c,i,0});
        g.pb({d,i,0});
        g.pb({e,i,0});
    }
    sort(g.begin(),g.end(),cmp);
    // for(int i=0;i<g.size();i++) cout<<i<<":"<<g[i].score<<" "<<g[i].id<<" "<<g[i].st<<"\n";

    int cnta=0,cntstu=0;
    for(int i=0,j=-1;i<5*n-n+1;i++){
        while(1){
            // cout<<i<<" "<<j<<" "<<cntstu<<" "<<cnta<<"\n";
            if(cntstu==n&&cnta<=k){
                ans=min(ans,g[i].score-g[j].score);
                // debug(i);debug(j);debug(g[i].score-g[j].score);
                break;
            }
            j++;
            if(j>=5*n) break;
            if(!cnt[g[j].id]) cntstu++;
            if(g[j].st){
                vis[g[j].id]=1;
                if(!cnt[g[j].id]) cnta++;
            }
            if(!g[j].st&&vis[g[j].id]&&cnt[g[j].id]==1) cnta--;
            cnt[g[j].id]++;
        }
        cnt[g[i].id]--;
        if(!cnt[g[i].id]) cntstu--;
        if(g[i].st){
            vis[g[i].id]=0;
            if(!cnt[g[i].id]) cnta--;
        }
        if(!g[i].st&&cnt[g[i].id]==1&&vis[g[i].id]) cnta++;
    }
    cout<<ans<<"\n";
}


int main(){
    ios::sync_with_stdio(0);cin.tie(0);
//    int t;cin>>t;while(t--)
    solve();
    return 0;
}