题目链接：https://ac.nowcoder.com/acm/contest/9983/B

排序左端点 然后如果同分数的话 A的分要往后排

双指针 一直维护一个区间，合法的时候再更新ans  因为是单增的序列 所以可以保证正确答案一定在这

连续的一段产生  但写起来很多细节需要注意

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e5+10;
 4 const int mod=1e9+7;
 5 #define ll long long
 6 #define pi pair<int,int>
 7 #define fi first
 8 #define sc second
 9 #define pb push_back
10 
11 struct ac
12 {
13     int v,f,p;// 分数 是否A 编号
14     bool operator<(ac a)
15     {
16         if(v==a.v) return f>a.f;
17         return v<a.v;
18     }
19 };
20 ac a[maxn*5];
21 int sum=0,cnt=0;// 学生总人数 用了多少个A
22 int vis[maxn];// 第i个人有没有用A
23 int kind[maxn];// 第i个人有几类分数
24 
25 
26 int main()
27 {
28     ios::sync_with_stdio(0);
29     cin.tie(0);
30     int n,k;
31     cin>>n>>k;
32     int tot=0;
33     for(int i=1;i<=n;i++)
34     {
35         for(int j=0;j<5;j++)
36         {
37             int x;
38             cin>>x;
39             a[++tot]={x,j,i};
40         }
41     }
42     sort(a+1,a+1+tot);
43     int ans=1e9;
44     int l=1;
45     for(int i=1;i<=tot;i++)
46     {
47         int f=a[i].f,p=a[i].p;
48         kind[p]++;
49         if(kind[p]==1) sum++;
50         if(!f)
51         {
52             vis[p]=1;
53             if(kind[p]==1)
54                 cnt++;
55         }
56         while(l<=i)
57         {
58             if(sum==n&&cnt<=k)
59             {
60                  ans=min(ans,a[i].v-a[l].v);
61             }
62             else break;
63             int p2=a[l].p,f2=a[l].f;
64             kind[p2]--;
65             if(kind[p2]==0) sum--;
66             if(kind[p2]==1&&vis[p2]) cnt++;
67             if(!f2&&!kind[p2]) cnt--;
68             l++;
69         }
70     }
71     cout<<ans<<'\n';
72 
73 
74 
75 
76 
77 
78 }

View Code