题目链接：https://codeforces.ml/gym/301256/problem/E
题意：t组测试用例，n个学生， 每个学生有俩种成绩（分为发挥好or不好），考试结束，取最高成绩*p%为合格成绩，问：成绩大于等于合格成绩的同学最多有多少个？
题解：
尺取
首先利用结构体存储每个成绩以及其对应的学生id编号，然后按照成绩大小排序
先遍历一次成绩，直到保证这些成绩的id号凑齐n个学生， 然后开始尺取，用一个while循环，每一次右界限向右移一个单位，再进行从左界限开始筛选，把不满足条件的成绩剔除。如此反复，直到右界限到达成绩尾端。
关键点：右界限的成绩就是最高成绩，注意使用long long, 否则成绩*100会爆int
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define ll long long 4 const int N = 4e5+5; 5 6 struct student { 7 int id; 8 ll val; 9 }; 10 student stu[N]; 11 int visit[N]; 12 13 bool cmp(student a, student b) { 14 return a.val < b.val; 15 } 16 17 int main() { 18 int t; 19 cin >> t; 20 for (int tt = 1; tt <= t; tt++) { 21 int n, p; 22 cin >> n >> p; 23 int kk = 1; 24 for (int i = 1; i <= n; i++) { 25 int min_score, max_score; 26 cin >> min_score >> max_score; 27 stu[kk++] = {i, min_score}; 28 stu[kk++] = {i, max_score}; 29 visit[i] = 0; 30 } 31 sort(stu+1, stu+kk, cmp); 32 int now = 0, left = 1, right = 1; 33 while (now != n) { 34 student temp = stu[right]; 35 if (visit[temp.id] == 0) now++; 36 visit[temp.id]++; 37 right++; 38 } 39 right--; 40 visit[stu[right].id]--; 41 now--; 42 int res = 1;//答案最少一个 43 while (right < kk) { 44 student temp = stu[right]; 45 if (visit[temp.id] == 0) now++; 46 visit[temp.id]++; 47 while (stu[left].val * 100 < temp.val * p) { 48 visit[stu[left].id]--; 49 if (visit[stu[left].id] == 0) now--; 50 left++; 51 } 52 res = max(res, now); 53 right++; 54 } 55 56 printf ("Case #%d: %d\n", tt, res); 57 } 58 return 0; 59 }
原文：https://www.cnblogs.com/mr-wei977955490/p/13938834.html