题目描述

Professor Alex is preparing an exam for his students now.

There will be n students participating in this exam. If student i has a good mindset, he/she will perform well and get a
​i
​​ points. Otherwise, he/she will get b
​i
​​ points. So it is impossible to predict the exam results. Assume the highest score of these students is x points. The students with a score of no less than x⋅p% will pass the exam.

Alex needs to know what is the maximum number of students who can pass the exam in all situations. Can you answer his question?

题意：

有n个人，每个人在状态好和不好时会得到两个成绩
及格线为最高分的p%，问最多几个人及格

题解：

方法很巧妙
用尺取的方法
首先将所有成绩（包括状态好和不好）排序
然后先从第一个成绩开始选出包含五个人的最小区间
然后从头指针head和尾指针tail
head不断判断是否满足条件

while(a[head].val*100<a[tail].val*p)

因为成绩是顺序排的，所以tail指向的成绩为最高成绩
然后从最低开始移动判断，如果不满足且区间内值包含他的一次成绩，就删去
因为每个人有两个成绩，好成绩一定排在坏成绩前面
具体看看图
图片说明
详细看代码

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int mx=1000010;

struct node{
    int id;
    ll val;
}a[mx];
int vis[mx];
ll n,p;
bool cmp(node q,node m)
{
    return q.val<m.val;
}
int main(){
    int t;
    cin>>t;
    for(int ca=1;ca<=t;ca++){
        cin>>n>>p;
        int tot=0;
        ll x,b;
        for(int i=1;i<=n;i++){
            cin>>x>>b;
            a[++tot]={i,x};
            a[++tot]={i,b};
            vis[i]=0;
        }
        cout<<"Case #"<<ca<<": ";
        // sort 按照从小到大排序 
        sort(a+1,a+1+tot,cmp);
        // now 表示当前 head 到 tail 这个范围中有多少个不同的节点 
        int now=0;
        int head=1,tail=0;

        //  尺取，先跑一个长度为 n的范围 
        while(now!=n){
            tail++;
            if(vis[a[tail].id]==0){
                now++;
            }
            vis[a[tail].id]++;
        }
        // 答案最少有一个。 
        int ans=1; 
        // 因为 进入 while 需要先加 所以要提前的 减一下 
        now--;
        vis[a[tail].id]--;
        tail--;

        while(tail<tot){
            // 尾指针向后移动一下 
            tail++;
            // 如果 这个数前面已经将去过了，头结点到这个范围没有 now++ 
            if(vis[a[tail].id]==0){
                now++;
            }
            vis[a[tail].id]++;
            // 进行尺取，只要不满足的就减去 
            while(a[head].val*100<a[tail].val*p){
                // 如果当前区间这个 id 的数就剩一个还不满足就 now-- 
                if(vis[a[head].id]==1){
                    now--;
                }
                vis[a[head].id]--;
                head++;
            }
            //　更新最大值 
            ans=max(ans,now);
        }
        cout<<ans<<"\n";
    }

    return 0;
}