20年秦皇島D - Exam Results（二分+思維，附易錯數據）

亞曆克斯教授正在為他的學生准備考試。

將會nn參加本次考試的學生。如果學生ii擁有良好的心態，他/她會錶現出色並獲得a_iai​分。否則，他/她會得到北京國際機場bi​分。所以不可能預測考試結果。假設這些學生的最高分是xx分。分數不低於的學生x \cdot p\%x⋅p%會通過考試的。

Alex需要知道在所有情况下能够通過考試的學生人數上限是多少。你能回答他的問題嗎？

投入

輸入的第一行給出了測試用例的數量，T\ (1次10^3)T (1≤T≤5×103). TT測試案例如下。

對於每個測試用例，第一行包含兩個整數n \(1 \ le n \ le 2 \次10^5)n (1≤n≤2×105)和p\ (1 \le p \le 100)p (1≤p≤100)，在哪裏nn是學生的數量p\%p%就是比例。

以下每一項nnlines包含兩個整數10^9阿樂大學ai​,bi​ (1≤bi​≤ai​≤109)，代錶學生的分數ii.

的總和nn在所有測試案例中，不超過5次10^55×105.

輸出

對於每個測試用例，輸出一行包含“案例#x: y“，哪裏\texttt{x}x是測試用例編號(從11)，以及\texttt{y}y是學生的最大數量。

樣本1

投入複制	輸出複制
2 2 50 2 1 5 1 5 60 8 5 9 3 14 2 10 8 7 6	Case #1: 2 Case #2: 4

題意：n個學生是較高分，或者是較低分。使不低於最高分*(m/100)的人數最多

思路：看別人都是尺取，差分什麼，但是不能理解，還好自己的代碼終於過了

個人覺得這個思路還是比較好理解的。

先結構體排序，按照高分高的（一樣的話按低分高的）進行排序，第二個樣例就成了下面這樣

struct Node
{
    int x,y;
    bool operator<(const Node temp)const{
        if(x!=temp.x) return x>temp.x;
        return y>temp.y;
    }
}x[M];

14 2
10 8
9 3
8 5
7 6

        如果最後的最大值是14，那麼其他一定都是最大的，二分查找上昇數組中有多少不低於14*(60/100.0)就很簡單

        如果最後的最大值是10，那麼下面的一定是最大的，第一個不是14，一定會是2，因為14存在的話10不會是最大的。那麼答案就是下面較大的答案+上面較小的答案。因為上面較小的答案是沒有順序的，而優先隊列不能進行二分查找，可以使用vector進行添加+二分查找，具體下面代碼最上面兩個函數就是。

然後對於數據：

2 50
100 80
7 6

7和6永遠不會是最大值，實現這個停止只需要記錄前面最大的y為maxxy，if(x[i].x<maxxy) break;即可

注意最後那個最大的maxxy也是有可能是最大，最後需要再算一遍結果，比如100 80,7 6這個數據，maxxy=80。

#include<bits/stdc++.h>
using namespace std;
#define fo(a,b) for(int i=a;i<=b;i++)
#define inf 0x3f3f3f3f
#define ll long long
const ll mod=998244353;
#define EXP 1e-6
#define M 1000005
int T,n,m,maxxy;
int a[M];
struct Node
{
    int x,y;
    bool operator<(const Node temp)const{
        if(x!=temp.x) return x>temp.x;
        return y>temp.y;
    }
}x[M];
vector<int>s;
void update(int q){        //差不多以優先隊列時間加入
    maxxy=max(maxxy,q);
    vector<int>::iterator last=lower_bound(s.begin(),s.end(),q);
    s.insert(last,q);
}
int solve(double a){        //二分查找
    if(s.size()==0) return 0;
    return lower_bound(s.begin(),s.end(),a)-s.begin();
}
signed main()
{
    scanf("%d",&T);
    for(int k=1;k<=T;k++){
        int maxx=0;
        maxxy=0;
        s.clear();
        scanf("%d%d",&n,&m);
        fo(1,n) scanf("%d%d",&x[i].x,&x[i].y);
        sort(x+1,x+n+1);
        fo(1,n) a[i]=x[n-i+1].x;
        for(int i=1;i<=n;i++){
            if(x[i].x<maxxy) break;        //如果較高分無法成為最大值
            double r=x[i].x*(m/100.0);
            int sum=(n-i)-(lower_bound(a+1,a+n+1-i,r)-a)+2;        //下面的
            sum+=i-solve(r)-1;        //上面的
            maxx=max(maxx,sum);
            update(x[i].y);
        }
        double r=maxxy*(m/100.0);
        int sum=0;
        for(int i=1;i<=n;i++){        //maxxy為最大值時的答案
            sum+=(x[i].x>maxxy?(x[i].y>=r):(x[i].x>=r));
        }
        maxx=max(maxx,sum);
        printf("Case #%d: %d\n",k,maxx);
    }
	return 0;
}

/*
一些易錯的數據：

1
3 50
100 6
5 4
6 4

:3

1
2 50
5 5
2 2

:2

1
3 50
100 6
5 4
5 4

:3
*/