Nowcoder9983B.内卷（双指针）

链接：https://ac.nowcoder.com/acm/contest/9983/B
来源：牛客网

在一个班级里有 $ii个同学在得到五个等级时预期的分数分别为ai,bi,ci,di,eia_{i},b_{i},c_{i},d_{i},e_{i}ai,bi,ci,di,ei。请问在最理想的情况且不违反上述条件的情况下，他们的预期分数最大值和最小值之差最小为多少。$

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int n,k;
int A[maxn],B[maxn],C[maxn],D[maxn],E[maxn];
set<int> st,sa;
map<int,int> mp,ma;
vector<pair<int,pair<int,int> > > v; 
int cnt;
int main () {
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++) scanf("%d%d%d%d%d",A+i,B+i,C+i,D+i,E+i);
    for (int i=1;i<=n;i++) {
        v.push_back(make_pair(A[i],make_pair(i,1)));
        v.push_back(make_pair(B[i],make_pair(i,2)));
        v.push_back(make_pair(C[i],make_pair(i,3)));
        v.push_back(make_pair(D[i],make_pair(i,4)));
        v.push_back(make_pair(E[i],make_pair(i,5)));
    }
    sort(v.begin(),v.end());
    int l=0,r=0;
    int ans=1e9;
    while (l<v.size()) {
        while (r<=v.size()) {
            if (r==v.size()||st.size()==n) {
                //如果当前已经有n个不同的人
                //同时只有a的人小于等于k
                //则更新答案 
                if (sa.size()<=k&&st.size()==n) {
                    //printf("%d %d %d %d
",sa.size(),l,r-1,v[r-1].first-v[l].first);
                    ans=min(ans,v[r-1].first-v[l].first);
                }
                break;
            }
            //如果这个人本来在区间不存在，就插入 
            if (!mp[v[r].second.first]) {
                st.insert(v[r].second.first);
            }    
            mp[v[r].second.first]++;
            
            //如果这个人的属性不是a，且他本来不存在除a以外的元素
            //就把他从sa里面删除
            //同时更新ma ma不为0表示他存在除a以外的元素 
            if (v[r].second.second!=1) {
                //如果第r元素不是A 
                if (!ma[v[r].second.first])    sa.erase(v[r].second.first);//如果它本身不存在除a以外的元素，现在存在了，就把它在sa里删掉 
                ma[v[r].second.first]++;
            }
            else if (v[r].second.second==1) {
                if (mp[v[r].second.first]==1) sa.insert(v[r].second.first);
            }
            r++;
        }
        //如果他是最后一个 ，就把他的信息从sa和st里面删掉 
        mp[v[l].second.first]--;
        if (!mp[v[l].second.first]) sa.erase(v[l].second.first),st.erase(v[l].second.first);
        //如果他不是最后一个，同时这个属性不为A，则ma里对应的项--
        //如果-完了， 
        else if (v[l].second.second!=1) {
            ma[v[l].second.first]--;//ma表示不存在除a以外的学生人数 
            if (!ma[v[l].second.first]) sa.insert(v[l].second.first);
        }
        
        l++;
    }
    printf("%d
",ans);
    //A不能超过k个
    //就用A最小的k个 
    //双指针
    //如果区间内刚好包含n个不同的人同时A的元素数小于等于k 
}

Nowcoder9983B.内卷（双指针）

相关推荐