Exam Results

題目大意

有 n 個人 每個人可以從兩個成績選一個做最終成績，及格成績是這n個人的成績中最大的成績 x*p%的值。問你最多有多少人及格。

解題思路

這個題，可以用尺取去解決，設一個頭指標，一個尾指標。每次移動一下尾指標看當前情況中有多少個及格人數。每次每次更新答案的最大值。這裡可以先進行排序沒然後吧每個人的成績分開存，非常巧妙的一個拆分。

#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;

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,[](node q,node m){
			return q.val<m.val;
		});
		// 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;
}